{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ugly Number III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nthUglyNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #丑数 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你四个整数：<code>n</code> 、<code>a</code> 、<code>b</code> 、<code>c</code> ，请你设计一个算法来找出第 <code>n</code> 个丑数。</p>\n",
    "\n",
    "<p>丑数是可以被 <code>a</code> <strong>或</strong> <code>b</code> <strong>或</strong> <code>c</code> 整除的 <strong>正整数</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, a = 2, b = 3, c = 5\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, a = 2, b = 3, c = 4\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, a = 2, b = 11, c = 13\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1000000000, a = 2, b = 217983653, c = 336916467\n",
    "<strong>输出：</strong>1999999984\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n, a, b, c <= 10^9</code></li>\n",
    "\t<li><code>1 <= a * b * c <= 10^18</code></li>\n",
    "\t<li>本题结果在 <code>[1, 2 * 10^9]</code> 的范围内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ugly-number-iii](https://leetcode.cn/problems/ugly-number-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ugly-number-iii](https://leetcode.cn/problems/ugly-number-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2\\n3\\n5', '4\\n2\\n3\\n4', '5\\n2\\n11\\n13']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        a,b,c = 0,0,0\n",
    "        dp = [1]*n\n",
    "        for i in range(1,n):\n",
    "            x,y,z = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i] = min(x,y,z)\n",
    "            if dp[i] == x:\n",
    "                a+=1\n",
    "            if dp[i] == y:\n",
    "                b+=1\n",
    "            if dp[i] == z:\n",
    "                c+=1\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res  = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]\n",
    "        rs  = set(res)\n",
    "        i = 0\n",
    "        chou = [2,3,5]\n",
    "        while len(rs)<n*4:\n",
    "            cl = len(res)\n",
    "            new_res = []\n",
    "            for j in range(i,len(res)):\n",
    "                for k in chou:\n",
    "                    curr = res[j]*k\n",
    "                    if curr not in rs:\n",
    "                        rs.add(curr)\n",
    "                        new_res.append(curr)  \n",
    "            #new_res.sort()\n",
    "            res.extend(new_res)\n",
    "        res.sort()\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        a = b = c =0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i] = min(n2,n3,n5)\n",
    "            if dp[i]==n2:\n",
    "                a = a + 1\n",
    "            if dp[i]==n3:\n",
    "                b = b + 1\n",
    "            if dp[i]==n5:\n",
    "                c = c + 1\n",
    "\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res=[1]*n\n",
    "        a,b,c=0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2:\n",
    "                a += 1\n",
    "            if res[i] == n3:\n",
    "                b += 1\n",
    "            if res[i] == n5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0, 1]\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            dp.append(min(dp[p2]*2, dp[p3]*3, dp[p5]*5))\n",
    "            if dp[-1] == dp[p2] * 2:\n",
    "                p2 += 1\n",
    "            if dp[-1] == dp[p3] * 3:\n",
    "                p3 += 1\n",
    "            if dp[-1] == dp[p5] * 5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "Min Heap\n",
    "\n",
    "T: O(N logN)\n",
    "S: O(N)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        minheap = [1]   # first node in min-heap is 1\n",
    "\n",
    "        for _ in range(n):\n",
    "            curr = heappop(minheap)\n",
    "            for factor in factors:\n",
    "                heappush(minheap, curr*factor)\n",
    "                if curr % factor == 0:\n",
    "                    break\n",
    "\n",
    "        return curr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        stack = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]\n",
    "        fa = [2,3,5]\n",
    "        if n <= 10:return stack[n-1]\n",
    "        t = n-10\n",
    "        for _ in range(t):\n",
    "            top = stack[-1]\n",
    "            nex = [inf]*3\n",
    "            for j,y in enumerate(fa):\n",
    "                for x in stack:\n",
    "                    if x*y > top:\n",
    "                        nex[j] = x*y\n",
    "                        break\n",
    "            minnex = min(nex)\n",
    "            stack.append(minnex)\n",
    "        #print(stack)\n",
    "        return stack[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # dp[i] 表示第i个丑数\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[1] = 1\n",
    "        p2, p3, p5 = 1, 1, 1\n",
    "        for i in range(2, n+1):\n",
    "            dp2 = dp[p2] * 2\n",
    "            dp3 = dp[p3] * 3\n",
    "            dp5 = dp[p5] * 5\n",
    "            cur = min(min(dp2, dp3), dp5)\n",
    "            if cur == dp2:\n",
    "                p2 += 1\n",
    "            if cur == dp3:\n",
    "                p3 += 1\n",
    "            if cur == dp5:\n",
    "                p5 += 1\n",
    "            dp[i] = cur\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = res[a] * 2,res[b] * 3 ,res[c] * 5\n",
    "            res[i] = min(n2,n3,n5)\n",
    "            if res[i] == n2:\n",
    "                a += 1\n",
    "            if res[i] == n3:\n",
    "                b += 1\n",
    "            if res[i] == n5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int) -> int:\n",
    "#         factors = [2, 3, 5]\n",
    "#         seen = [1]\n",
    "#         heap = [1]\n",
    "\n",
    "#         for _ in range(1, n):\n",
    "#             curr = heapq.heappop(heap)\n",
    "#             for factor in factors:\n",
    "#                 nxt = curr * factor\n",
    "#                 if nxt not in seen:\n",
    "#                     seen.append(nxt)\n",
    "#                     heapq.heappush(heap, nxt)\n",
    "        \n",
    "#         return heapq.heappop(heap)\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1] * n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        idx_table = [0,0,0]\n",
    "        x2,x3,x5 = 2,3,5\n",
    "        ug_number = [1]\n",
    "        while(n>1):\n",
    "            min_x = min(x2,x3,x5)\n",
    "            ug_number.append(min_x)\n",
    "            if x2==min_x:\n",
    "                idx_table[0]+=1\n",
    "                x2 = ug_number[idx_table[0]]*2\n",
    "            if x3==min_x:\n",
    "                idx_table[1]+=1\n",
    "                x3 = ug_number[idx_table[1]]*3\n",
    "            if x5==min_x:\n",
    "                idx_table[2]+=1\n",
    "                x5 = ug_number[idx_table[2]]*5\n",
    "            n-=1\n",
    "        return ug_number[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        a = [1]\n",
    "        for i in range(n):\n",
    "            x,y,z = a[p2]*2,a[p3]*3,a[p5]*5\n",
    "            minnum = min(x,y,z)\n",
    "            a.append(minnum)\n",
    "            if x == minnum:\n",
    "                p2+=1\n",
    "            if y ==minnum:\n",
    "                p3+=1\n",
    "            if z == minnum:\n",
    "                p5+=1\n",
    "        return a[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        \n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "        for i in range(2, n + 1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(dp[a]*2, dp[b]*3, dp[c]*5)\n",
    "            if dp[i]==dp[a]*2:\n",
    "                a += 1\n",
    "            if dp[i]==dp[b]*3:\n",
    "                b += 1\n",
    "            if dp[i]==dp[c]*5:\n",
    "                c += 1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n):\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5\n",
    "            dp[i]=min(n2,n3,n5)\n",
    "            if dp[i] == n2:\n",
    "                a+=1\n",
    "            if dp[i] == n3:\n",
    "                b+=1\n",
    "            if dp[i] == n5:\n",
    "                c+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "        for i in range(2,n+1):\n",
    "            num2,num3,num5 = dp[p2] * 2,dp[p3] * 3,dp[p5] * 5\n",
    "            dp[i] = min(num2,num3,num5)\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3: #不能用else\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        a = [1]\n",
    "        for i in range(n):\n",
    "            x,y,z = a[p2]*2,a[p3]*3,a[p5]*5\n",
    "            minnum = min(x,y,z)\n",
    "            a.append(minnum)\n",
    "            if x == minnum:\n",
    "                p2+=1\n",
    "            if y ==minnum:\n",
    "                p3+=1\n",
    "            if z == minnum:\n",
    "                p5+=1\n",
    "        return a[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 每一个丑数都可以通过之前的丑数x3，x5，x2得到\n",
    "        # 为了保证严重递增，每次都是生成之前的最小值\n",
    "        res = [1] * n\n",
    "        a, b, c = 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        \n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def minX(num1,num2,num3):\n",
    "    x = num1[0]\n",
    "    y = num2[0]\n",
    "    z = num3[0]\n",
    "    res = min(x,y,z)\n",
    "    if res ==x: num1 = num1[1:]\n",
    "    if res == y: num2 = num2[1:]\n",
    "    if res == z: num3 = num3[1:]\n",
    "\n",
    "    return num1, num2, num3, res\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n ==1: return 1\n",
    "        res = [1]\n",
    "        x = 1\n",
    "        add_num = None\n",
    "        num1 = [i*2 for i in res]\n",
    "        num2 = [i*3 for i in res]\n",
    "        num3 = [i*5 for i in res]\n",
    "        while x < n:\n",
    "            num1, num2, num3 , add_num = minX(num1, num2, num3)\n",
    "            res.append(add_num)\n",
    "            x += 1\n",
    "            num1.append(add_num*2)\n",
    "            num2.append(add_num*3)\n",
    "            num3.append(add_num*5)\n",
    "        return add_num\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1]*n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        visited = defaultdict(lambda: False)\n",
    "        pq = [1]\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            c = heapq.heappop(pq)\n",
    "            for nxt in [c*2, c*3, c*5]:\n",
    "                if not visited[nxt]:\n",
    "                    visited[nxt] = True\n",
    "                    heapq.heappush(pq, nxt)\n",
    "\n",
    "        return pq[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        nums = [2, 3, 5]\n",
    "        heap = [1]\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for k in nums:\n",
    "                n = k * cur\n",
    "                if n not in heap:\n",
    "                    heapq.heappush(heap, k * cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        temp = [1]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        k = 0\n",
    "        z = 1\n",
    "        while z < n:\n",
    "            st = min(temp[i]*2, temp[j]*3, temp[k]*5)\n",
    "            if st == temp[i]*2:\n",
    "                i+=1\n",
    "            elif st == temp[j]*3:\n",
    "                j+=1\n",
    "            else:\n",
    "                k+=1\n",
    "            if st == temp[-1]:\n",
    "                continue\n",
    "            temp.append(st)\n",
    "            z+=1\n",
    "            \n",
    "        return temp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        l = [1]*n\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5 = l[a]*2,l[b]*3,l[c]*5\n",
    "            l[i] = min(n2,n3,n5)\n",
    "            if l[i] == n2:\n",
    "                a+=1\n",
    "            if l[i] == n3:\n",
    "                b+=1\n",
    "            if l[i] == n5:\n",
    "                c+=1\n",
    "        return l[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [1 for i in range(n)]\n",
    "        i,j,k = 0,0,0\n",
    "        for idx in range(1,n):\n",
    "            # ic = jc = kc =False\n",
    "            c1 = dp[i]*2 if dp[i]*2>dp[idx-1] else float('inf')\n",
    "            c2 = dp[j]*3 if dp[j]*3>dp[idx-1] else float('inf')\n",
    "            c3 = dp[k]*5 if dp[k]*5>dp[idx-1] else float('inf')\n",
    "            # c4 = dp[i]*3 if dp[i]*3>dp[idx-1] else float('inf')\n",
    "            # c5 = dp[j]*3 if dp[j]*3>dp[idx-1] else float('inf')\n",
    "            # c6 = dp[k]*3 if dp[k]*3>dp[idx-1] else float('inf')\n",
    "            # c7 = dp[i]*5 if dp[i]*5>dp[idx-1] else float('inf')\n",
    "            # c8 = dp[j]*5 if dp[j]*5>dp[idx-1] else float('inf')\n",
    "            # c9 = dp[k]*5 if dp[k]*5>dp[idx-1] else float('inf')\n",
    "            dp[idx] = min(c1,c2,c3)#,c4,c5,c6,c7,c8,c9)\n",
    "            if c1==dp[idx]  : i+=1\n",
    "            if c2==dp[idx] :j+=1\n",
    "            if c3==dp[idx] :k+=1\n",
    "\n",
    "            # i+= 1 if ic and ((jc and i<=j) or ( kc and i<=k ) or (not (jc or kc))) else 0\n",
    "            # j+= 1 if jc and ((kc and j<=k) or ( ic and j<=i ) or (not (ic or kc))) else 0\n",
    "            # k+= 1 if kc and ((jc and k<=j) or ( ic and k<=i ) or (not (jc or ic))) else 0\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        res = [0,1,2,3,4,5,6]\n",
    "        i2, i3, i5 = 4, 3, 2\n",
    "        for _ in range(7, n + 1):\n",
    "            tx = 2 * res[i2], 3 * res[i3], 5 * res[i5]\n",
    "            x = min(tx)\n",
    "            if x == tx[0]: i2 += 1\n",
    "            if x == tx[1]: i3 += 1\n",
    "            if x == tx[2]: i5 += 1\n",
    "            res.append(x)\n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] =1\n",
    "        p1=p2=p3=1\n",
    "        for i in range(2,n+1):\n",
    "            ans = min(dp[p1]*2,dp[p2]*3,dp[p3]*5)\n",
    "            dp[i] = ans\n",
    "            if dp[i] == dp[p1]*2:\n",
    "                p1+=1\n",
    "            if dp[i] == dp[p2]*3:\n",
    "                p2+=1\n",
    "            if dp[i] == dp[p3]*5:\n",
    "                p3+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1] * n \n",
    "        idx2, idx3, idx5 = 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(2 * dp[idx2], 3 * dp[idx3], 5 * dp[idx5])\n",
    "            idx2 += 1 if dp[i] == 2 * dp[idx2] else 0\n",
    "            idx3 += 1 if dp[i] == 3 * dp[idx3] else 0\n",
    "            idx5 += 1 if dp[i] == 5 * dp[idx5] else 0\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        a=[2,3,5]\n",
    "        b=[1,1,1]\n",
    "        c=[1]\n",
    "        d=[2,3,5]\n",
    "        for _ in range(n-1):\n",
    "            z=min(a)\n",
    "            c.append(z)\n",
    "            for i in range(3):\n",
    "                if a[i]==z:\n",
    "                    a[i]=d[i]*c[b[i]]\n",
    "                    b[i]+=1\n",
    "        return (c[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res,a,b,c=[1]*n,0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5=res[a]*2,res[b]*3,res[c]*5\n",
    "            res[i]=min(n2,n3,n5)\n",
    "            if n2==res[i]:a+=1\n",
    "            if n3==res[i]:b+=1\n",
    "            if n5==res[i]:c+=1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_numbers = [1]\n",
    "        i2,i3,i5 = 0,0,0\n",
    "        while len(ugly_numbers) < n:\n",
    "            next2 = ugly_numbers[i2] * 2\n",
    "            next3 = ugly_numbers[i3] * 3\n",
    "            next5 = ugly_numbers[i5] * 5\n",
    "\n",
    "            next_min = min(next2,next3,next5)\n",
    "            ugly_numbers.append(next_min)\n",
    "            if next_min == next2:\n",
    "                i2+=1\n",
    "            if next_min == next3:\n",
    "                i3+=1\n",
    "            if next_min == next5:\n",
    "                i5+=1\n",
    "\n",
    "        # print(ugly_numbers)\n",
    "        return ugly_numbers[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        table = []\n",
    "        que = []\n",
    "        heapq.heapify(que)\n",
    "        heapq.heappush(que,1)\n",
    "        while len(table) < n:\n",
    "            g = heapq.heappop(que)\n",
    "            table.append(g)\n",
    "            for i in 2,3,5:\n",
    "                ans = g*i\n",
    "                if ans not in que:\n",
    "                    heapq.heappush(que,ans)\n",
    "    \n",
    "        return table[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_numbers = [1]\n",
    "        i2,i3,i5 = 0,0,0\n",
    "\n",
    "        while len(ugly_numbers) < n:\n",
    "            n2,n3,n5 = ugly_numbers[i2]*2,ugly_numbers[i3]*3,ugly_numbers[i5]*5\n",
    "            nmin = min(n2,n3,n5)\n",
    "            ugly_numbers.append(nmin)\n",
    "            if nmin == n2:\n",
    "                i2 += 1\n",
    "            if nmin == n3:\n",
    "                i3 += 1\n",
    "            if nmin == n5:\n",
    "                i5 += 1\n",
    "        \n",
    "        return ugly_numbers[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 用还没乘过 2 的最小丑数乘以 2；用还没乘过 3 的最小丑数乘以 3；用还没乘过 5 的最小丑数乘以 5。然后在得到的数字中取最小，就是新的丑数。\n",
    "    #### 3 个指针 index2, index3, index5 分别表示丑数集合中还没乘过 2，3，5 的丑数位置。\n",
    "\n",
    "\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res,a,b,c=[1]*n,0,0,0\n",
    "        for i in range(1,n):\n",
    "            n2,n3,n5=res[a]*2,res[b]*3,res[c]*5\n",
    "            res[i]=min(n2,n3,n5)\n",
    "            if res[i]==n2: a+=1\n",
    "            if res[i]==n3: b+=1\n",
    "            if res[i]==n5: c+=1\n",
    "        return res[-1]\n",
    "        # res, a, b, c = [1] * n, 0, 0, 0\n",
    "        # for i in range(1, n):\n",
    "        #     n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "        #     res[i] = min(n2, n3, n5)\n",
    "        #     if res[i] == n2: a += 1\n",
    "        #     if res[i] == n3: b += 1\n",
    "        #     if res[i] == n5: c += 1\n",
    "        # return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[1] = 1\n",
    "        p2, p3, p5 = 1, 1, 1\n",
    "        for i in range(2, n+1):\n",
    "            n2, n3, n5 = dp[p2]*2, dp[p3]*3, dp[p5]*5\n",
    "            dp[i] = min(n2, n3, n5)\n",
    "            if dp[i] == n2:\n",
    "                p2 += 1\n",
    "            if dp[i] == n3:\n",
    "                p3 += 1\n",
    "            if dp[i] == n5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        ugly_numbers = [1]\n",
    "        i2 = i3 = i5 = 0\n",
    "\n",
    "        while len(ugly_numbers) < n:\n",
    "            next2 = ugly_numbers[i2] * 2\n",
    "            next3 = ugly_numbers[i3] * 3\n",
    "            next5 = ugly_numbers[i5] * 5\n",
    "\n",
    "            next_ugly = min(next2, next3, next5)\n",
    "            ugly_numbers.append(next_ugly)\n",
    "\n",
    "            if next_ugly == next2:\n",
    "                i2 += 1\n",
    "            if next_ugly == next3:\n",
    "                i3 += 1\n",
    "            if next_ugly == next5:\n",
    "                i5 += 1\n",
    "\n",
    "        return ugly_numbers[-1]\n",
    "\n",
    "# Testing the function with an example\n",
    "sol = Solution()\n",
    "sol.nthUglyNumber(10)  # Example: Find the 10th ugly number\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] =1\n",
    "        p1=p2=p3=1\n",
    "        for i in range(2,n+1):\n",
    "            ans = min(dp[p1]*2,dp[p2]*3,dp[p3]*5)\n",
    "            dp[i] = ans\n",
    "            if dp[i] == dp[p1]*2:\n",
    "                p1+=1\n",
    "            if dp[i] == dp[p2]*3:\n",
    "                p2+=1\n",
    "            if dp[i] == dp[p3]*5:\n",
    "                p3+=1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "limit=1690\n",
    "uglyNums=[1]\n",
    "p2,p3,p5=0,0,0\n",
    "for i in range(limit - 1):\n",
    "    n2,n3,n5 = uglyNums[p2]*2,uglyNums[p3]*3,uglyNums[p5]*5\n",
    "    uglyNums.append(min(n2, n3, n5))\n",
    "    if n2 == uglyNums[-1]:\n",
    "        p2 += 1\n",
    "    if n3 == uglyNums[-1]:\n",
    "        p3 += 1\n",
    "    if n5 == uglyNums[-1]:\n",
    "        p5 += 1\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        return uglyNums[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        pq = [1]\n",
    "        s = set()\n",
    "        for i in range(n - 1):\n",
    "            tmp = heapq.heappop(pq)\n",
    "            for j in [2,3,5]:\n",
    "                if tmp * j not in s:\n",
    "                    heapq.heappush(pq, tmp * j)\n",
    "                    s.add(tmp * j)\n",
    "        return heapq.heappop(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        result=[1]\n",
    "        id2=id3=id5=0\n",
    "        for i in range(n-1):\n",
    "            result.append(min(result[id2]*2,result[id3]*3,result[id5]*5))\n",
    "            if result[-1]==2*result[id2]:\n",
    "                id2+=1\n",
    "            if result[-1]==3*result[id3]:\n",
    "                id3+=1\n",
    "            if result[-1]==5*result[id5]:\n",
    "                id5+=1\n",
    "        return result[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ans = [1]\n",
    "        for i in range(n):\n",
    "            for j in [2,3,5]:\n",
    "                if ans[i] * j not in ans:\n",
    "                    ans.append(ans[i] * j)\n",
    "            ans = sorted(ans)\n",
    "        return ans[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 根据题意，每个丑数都可以由其他较小的丑数通过乘以2或3或5得到\n",
    "        # dp[i]表示第i个丑数\n",
    "        # dp[1] = 1\n",
    "        # 定义三个指针p2 p3 p5表示下一个丑数是当前指针指向的丑数乘以对应的质因数，初始时 三个指针都是1\n",
    "        # transition dp[1] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5) 比较dp[i]和dp[p2]*2, dp[p3]*3, dp[p5]*5是否相等，相等就将对应的指针+1\n",
    "\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        p2 = p3 = p5 = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5\n",
    "            dp[i] = min(num2, num3, num5)\n",
    "            # 看最小的数字是哪个，找到以后就把那个位置+1;相当于把每个位置都*2 *3 *5然后按照顺序排列\n",
    "            if dp[i] == num2:\n",
    "                p2 += 1\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = min(2*dp[p2],3*dp[p3],5*dp[p5])\n",
    "            if dp[i] == 2*dp[p2]:p2+=1\n",
    "            if dp[i] == 3*dp[p3]:p3+=1\n",
    "            if dp[i] == 5*dp[p5]:p5+=1\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        p2=p3=p5=1\n",
    "        for i in range(2,n+1):\n",
    "            dp2=dp[p2]*2\n",
    "            dp3=dp[p3]*3\n",
    "            dp5=dp[p5]*5\n",
    "            Min=min(dp2,dp3,dp5)\n",
    "            dp[i]=Min\n",
    "            if dp2==Min:\n",
    "                p2+=1\n",
    "            if dp3==Min:\n",
    "                p3+=1\n",
    "            if dp5==Min:\n",
    "                p5+=1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]\n",
    "        a = b = c = 0\n",
    "        for _ in range(1, n):\n",
    "            num = min(res[a] * 2, res[b] * 3, res[c] * 5)\n",
    "            res.append(num)\n",
    "            if num == res[a] * 2:\n",
    "                a += 1\n",
    "            if num == res[b] * 3:\n",
    "                b += 1\n",
    "            if num == res[c] * 5:\n",
    "                c += 1\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [0] * (n+1)\n",
    "        res[0] = 1\n",
    "        i, j, k = 0, 0, 0\n",
    "        for idx in range(1, n):\n",
    "            t = min(res[i] * 2, res[j] * 3, res[k] * 5)\n",
    "            res[idx] = t\n",
    "            if t == res[i] * 2:\n",
    "                i += 1\n",
    "            if t == res[j] * 3:\n",
    "                j += 1\n",
    "            if t == res[k] * 5:\n",
    "                k += 1\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = {2,3,5}\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(n-1):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                n = cur * factor\n",
    "                if n not in seen:\n",
    "                    seen.add(n)\n",
    "                    heapq.heappush(heap, n)\n",
    "        \n",
    "        return heapq.heappop(heap)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        i,j,k=0,0,0\n",
    "\n",
    "        ugly_nums = []\n",
    "\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        ugly_nums.append(1)\n",
    "        \n",
    "        for _ in range(1, n):\n",
    "            t2 = ugly_nums[i]*2\n",
    "            t3 = ugly_nums[j]*3\n",
    "            t5 = ugly_nums[k]*5\n",
    "\n",
    "            tmp = min(t2, t3, t5)\n",
    "            ugly_nums.append(tmp)\n",
    "            \n",
    "            if tmp == t2:\n",
    "                i += 1\n",
    "            \n",
    "            if tmp == t3:\n",
    "                j += 1\n",
    "            \n",
    "            if tmp == t5:\n",
    "                k += 1\n",
    "\n",
    "        return ugly_nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ret, a, b, c = [1] * n, 0, 0, 0\n",
    "        num = [2, 3, 5]\n",
    "        for i in range(1, n):\n",
    "            n1 = num[0] * ret[a]\n",
    "            n2 = num[1] * ret[b]\n",
    "            n3 = num[2] * ret[c]\n",
    "            ret[i] = min(n1, n2, n3)\n",
    "            if ret[i] == n1:\n",
    "                a += 1\n",
    "            if ret[i] == n2:\n",
    "                b += 1\n",
    "            if ret[i] == n3:\n",
    "                c += 1\n",
    "        return ret[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res, a, b, c = [1] * n, 0, 0, 0\n",
    "        for i in range(1, n):\n",
    "            n2, n3, n5 = res[a] * 2, res[b] * 3, res[c] * 5\n",
    "            res[i] = min(n2, n3, n5)\n",
    "            if res[i] == n2: a += 1\n",
    "            if res[i] == n3: b += 1\n",
    "            if res[i] == n5: c += 1\n",
    "        return res[-1]\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/problems/ugly-number-ii/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        table = [1]\n",
    "        que = []\n",
    "        heapq.heapify(que)\n",
    "        heapq.heappush(que,1)\n",
    "        while len(table) < n*2:\n",
    "            g = heapq.heappop(que)\n",
    "            for i in 2,3,5:\n",
    "                ans = g*i\n",
    "                if ans not in table:\n",
    "                    table.append(ans)\n",
    "                    heapq.heappush(que,ans)\n",
    "        table.sort()\n",
    "        return table[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 最小堆+哈希\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        seen = {1}\n",
    "        pq = [1]\n",
    "        for _ in range(n - 1):\n",
    "            curr = heapq.heappop(pq)\n",
    "            for factor in factors:\n",
    "                next = curr * factor\n",
    "                if next not in seen:\n",
    "                    seen.add(next)\n",
    "                    heapq.heappush(pq, next)\n",
    "        return heapq.heappop(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "        res = [1]\n",
    "        seen = set()\n",
    "        seen.add(1)\n",
    "\n",
    "        heap = [1]\n",
    "        res = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            res = heapq.heappop(heap)\n",
    "            print(res)\n",
    "\n",
    "            n2 = res * 2\n",
    "            if n2 not in seen:\n",
    "                heapq.heappush(heap, n2)\n",
    "                seen.add(n2)\n",
    "            n3 = res * 3\n",
    "            if n3 not in seen:\n",
    "                heapq.heappush(heap, n3)\n",
    "                seen.add(n3)\n",
    "            n5 = res * 5\n",
    "            if n5 not in seen:\n",
    "                heapq.heappush(heap, n5)\n",
    "                seen.add(n5)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ugly = [1, ]\n",
    "        seen = set([1])\n",
    "        factors = [2, 3, 5]\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            cur = heapq.heappop(ugly)\n",
    "            for f in factors:\n",
    "                new = cur * f\n",
    "                if new not in seen:\n",
    "                    seen.add(new)\n",
    "                    heapq.heappush(ugly, new)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        ans = [1]\n",
    "        index = 0\n",
    "        map1 = {}\n",
    "        map1[1] = 1\n",
    "\n",
    "        while index < n:\n",
    "\n",
    "            \n",
    "            map1[ans[index]*2] =1 if ans[index]*2 in map1 else ans.append(ans[index]*2)\n",
    "\n",
    "           \n",
    "            map1[ans[index]*3] =1 if ans[index]*3 in map1 else ans.append(ans[index]*3)\n",
    "\n",
    "            map1[ans[index]*4] =1 if ans[index]*4 in map1 else ans.append(ans[index]*4)\n",
    "\n",
    "            \n",
    "            map1[ans[index]*5] =1 if ans[index]*5 in map1 else ans.append(ans[index]*5)\n",
    "\n",
    "            index +=1\n",
    "            ans.sort()\n",
    "\n",
    "        return ans[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        seen = {1}\n",
    "        hq = [1]\n",
    "        factors = [2, 3, 5]\n",
    "        for _ in range(n-1):\n",
    "            cur = heappop(hq)\n",
    "            for factor in factors:\n",
    "                if (nxt:= factor * cur) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heappush(hq, nxt)\n",
    "        return heappop(hq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        tmp = {1,2,3,4,5,6}\n",
    "        res = [0,1,2,3,4,5,6]\n",
    "        x = [4, 3, 2]\n",
    "        for _ in range(7, n + 1):\n",
    "            while True:\n",
    "                tx = 2 * res[x[0]], 3 * res[x[1]], 5 * res[x[2]]\n",
    "                resx = min(tx)\n",
    "                x[tx.index(resx)] += 1\n",
    "                if resx in tmp:\n",
    "                    continue\n",
    "                tmp.add(resx)\n",
    "                res.append(resx)\n",
    "                break\n",
    "              \n",
    "        return resx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        factors = [2, 3, 5]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "        factors = [2,3,5]\n",
    "        for i in range(n-1):\n",
    "            cur = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if cur*factor not in seen:\n",
    "                    seen.add(cur*factor)\n",
    "                    heapq.heappush(heap,cur*factor)\n",
    "        \n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "\n",
    "        heap = []\n",
    "        res = []\n",
    "        seen = set([1, 2, 3, 5])\n",
    "\n",
    "        heapq.heappush(heap, 1)\n",
    "        heapq.heappush(heap, 2)\n",
    "        heapq.heappush(heap, 3)\n",
    "        heapq.heappush(heap, 5)\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            num = heapq.heappop(heap)\n",
    "            res.append(num)\n",
    "\n",
    "            if num * 2 not in seen:\n",
    "                seen.add(num * 2)\n",
    "                heapq.heappush(heap, num * 2)\n",
    "            if num * 3 not in seen:\n",
    "                seen.add(num * 3)\n",
    "                heapq.heappush(heap, num * 3)\n",
    "            if num * 5 not in seen:\n",
    "                seen.add(num * 5)\n",
    "                heapq.heappush(heap, num * 5)\n",
    "        \n",
    "        return res[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ugly = [1]\n",
    "        factor = [2, 3, 5]\n",
    "        i = 1\n",
    "        s = set()\n",
    "        while i < n:\n",
    "            front = heappop(ugly)\n",
    "            for f in factor:\n",
    "                if not f * front in s:\n",
    "                    s.add(f * front)\n",
    "                    heappush(ugly, front * f)\n",
    "            i += 1\n",
    "        return heappop(ugly)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        arr = [1]\n",
    "        factors = [2,3,4,5]\n",
    "        _set = set()\n",
    "        for i in range(n-1):\n",
    "            v = heapq.heappop(arr)\n",
    "            for f in factors:\n",
    "                num = v * f\n",
    "                if num not in _set:\n",
    "                    _set.add(num)\n",
    "                    heapq.heappush(arr, num)\n",
    "        return heapq.heappop(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        res = [1]\n",
    "        heapq.heapify(res)\n",
    "        helset = {1}\n",
    "        \n",
    "        for _ in range(n-1):\n",
    "            cur = heapq.heappop(res)\n",
    "            tem =[cur * 3,cur * 5, cur*2]\n",
    "            for k in tem:\n",
    "                if k not in helset:\n",
    "                    helset.add(k)\n",
    "                    heapq.heappush(res,k)\n",
    "            # if tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # tem = res[i] * 3\n",
    "            # if len(res)<=n and tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # tem = res[i] * 5\n",
    "            # if len(res)<=n and tem not in helset:\n",
    "            #     heapq.heappush(res,tem)\n",
    "            #     helset.add(tem)\n",
    "            # i+=1\n",
    "        \n",
    "        return heapq.heappop(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        base = [2, 3, 5]\n",
    "        seen = {1}  # already exist in the heap\n",
    "        heap = [1]  # to create a heap\n",
    "        for i in range(n-1):\n",
    "            min = heapq.heappop(heap)\n",
    "            seen.add(min)\n",
    "            for fact in base:\n",
    "                if (nxt := fact * min) in seen:\n",
    "                    continue\n",
    "                heapq.heappush(heap, nxt)\n",
    "                seen.add(nxt)\n",
    "        return heapq.heappop(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "解法一:优先队列\n",
    "\n",
    "每次从队列中取出最小值x\n",
    "将x分别和2/3/5相乘的结果入对，若是已经入队过，就不需要再次入队了。\n",
    "取出的第n次直接返回，\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        # 丑数的三个质因子\n",
    "        nums = [2, 3, 5]\n",
    "        # 记录已经入队的丑数\n",
    "        seen = {1}\n",
    "        # 初始化队列，第一个丑数是1\n",
    "        pq = [1]\n",
    "        # 从1开始，遍历n次\n",
    "        for i in range(1, n + 1):\n",
    "            # 每次从队列中取出最小数\n",
    "            x = heapq.heappop(pq)\n",
    "            # 第n次返回\n",
    "            if i == n:\n",
    "                return x\n",
    "            else:\n",
    "                # 将每次取出的丑数与质因子相乘\n",
    "                for num in nums:\n",
    "                    t = num * x\n",
    "                    # 将没有出现过的丑数入队\n",
    "                    if t not in seen:\n",
    "                        seen.add(t)\n",
    "                        heapq.heappush(pq, t)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        l=[1]\n",
    "        a,b,c=0,0,0\n",
    "        for i in range(1,n):\n",
    "            la,lb,lc=l[a]*2,l[b]*3,l[c]*5\n",
    "            t=min(la,lb,lc)\n",
    "            l.append(t)\n",
    "            if t==la: a+=1\n",
    "            if t==lb: b+=1\n",
    "            if t==lc: c+=1\n",
    "        print(l)\n",
    "        return l[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        heap = []\n",
    "        heapq.heappush(heap,1)\n",
    "\n",
    "        ug = 1\n",
    "        factors = {2,3,5}\n",
    "        seen = set()\n",
    "\n",
    "        res = []\n",
    "        for i in range(1699):\n",
    "            ug = heappop(heap)\n",
    "            res.append(ug)\n",
    "            for factor in factors:\n",
    "                if ug*factor not in seen:\n",
    "                    seen.add(ug*factor)\n",
    "                    heapq.heappush(heap,ug*factor)\n",
    "        \n",
    "        return res[n-1]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        c = set()\n",
    "        m = 1\n",
    "        stack = [1]\n",
    "        d = []\n",
    "        while len(d) < n:\n",
    "            m = min(stack)\n",
    "            stack.remove(m)\n",
    "            d.append(m)\n",
    "            if m * 2 not in c:\n",
    "                stack.append(m * 2)\n",
    "                c.add(m * 2)\n",
    "            if m * 3 not in c:\n",
    "                stack.append(m * 3)\n",
    "                c.add(m * 3)\n",
    "            if m * 5 not in c:\n",
    "                stack.append(m * 5)\n",
    "                c.add(m * 5)\n",
    "        return d[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        choushu=[2,3,5]\n",
    "        chouset=set()\n",
    "        for i in range(500):\n",
    "            for j in range(i+1):\n",
    "                a=choushu[i]*choushu[j]\n",
    "                if a not in chouset:\n",
    "                    choushu.append(a)\n",
    "                    chouset.add(a)\n",
    "        choushu=[1]+sorted(choushu)\n",
    "        return choushu[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        hash = defaultdict(int)\n",
    "        q = SortedList()\n",
    "        q.add(1)\n",
    "        hash[1] = 1\n",
    "        f = [2,3,5]\n",
    "        for i in range(1 ,n+1):\n",
    "            # print(\"___\", q,)\n",
    "            ele = q.pop(0)\n",
    "            if i == n:\n",
    "                return ele\n",
    "            for j in range(0,3):\n",
    "                next_ele = ele * f[j]\n",
    "                # print(\"next_ele : \", next_ele)\n",
    "                if hash[next_ele] == 0:\n",
    "                    hash[next_ele] = 1\n",
    "                    q.add(next_ele)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# /**\n",
    "#  * @param {number} n\n",
    "#  * @return {boolean}\n",
    "#  */\n",
    "# var nthUglyNumber = function(n) {\n",
    "#     if(n===1) return 1\n",
    "#     const hash = {}\n",
    "#     const queue= new MinPriorityQueue()\n",
    "#     queue.enqueue(1)\n",
    "#     hash[1] = true\n",
    "#     const f = [2,3,5]\n",
    "#     // let num = undefined\n",
    "#     for(let i=1; i<=n; i++) {\n",
    "#         const num = queue.dequeue().priority\n",
    "#         // console.log(queue.toArray())\n",
    "#         if(i===n) return num\n",
    "#         for(let j=0; j<3;j++) {\n",
    "#             const next = num * f[j]\n",
    "#             if(!hash[next]) {\n",
    "#                 hash[next] = true\n",
    "#                 queue.enqueue(next)\n",
    "#             }\n",
    "#         }\n",
    "#     }\n",
    "# };"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        \"\"\" 使用最小堆heapq\n",
    "        \"\"\"\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        num_set = set()\n",
    "        num_set.add(1)\n",
    "        trace_list = [1]\n",
    "        heapq.heapify(trace_list)\n",
    "        smallest_ugly = 1\n",
    "\n",
    "        i = 0\n",
    "        while i != n:\n",
    "            smallest_ugly = heapq.heappop(trace_list)\n",
    "            print(smallest_ugly)\n",
    "            if smallest_ugly*2 not in num_set:\n",
    "                num_set.add(smallest_ugly*2)\n",
    "                heapq.heappush(trace_list, smallest_ugly*2)\n",
    "            if smallest_ugly*3 not in num_set:\n",
    "                num_set.add(smallest_ugly*3)\n",
    "                heapq.heappush(trace_list, smallest_ugly*3)\n",
    "            if smallest_ugly*5 not in num_set:\n",
    "                num_set.add(smallest_ugly*5)\n",
    "                heapq.heappush(trace_list, smallest_ugly*5)\n",
    "            i += 1\n",
    "        return smallest_ugly\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        b = [2,3,5]\n",
    "        s = {2,3,5}\n",
    "        heapq.heapify(b)\n",
    "        n-=1\n",
    "        a=0\n",
    "        while n>0:\n",
    "            a=heapq.heappop(b)\n",
    "            if a*2 not in s:\n",
    "                s.add(a*2)\n",
    "                heapq.heappush(b,a*2)\n",
    "            if a*3 not in s:\n",
    "                s.add(a*3)\n",
    "                heapq.heappush(b,a*3)\n",
    "            if a*5 not in s:\n",
    "                s.add(a*5)\n",
    "                heapq.heappush(b,a*5)\n",
    "            n-=1\n",
    "            print(a)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp=[0,1]\n",
    "        p2=p3=p5=1\n",
    "        i=0\n",
    "        while len(dp)<n+1:\n",
    "            num2=2*dp[p2]\n",
    "            num3=3*dp[p3]  \n",
    "            num5=5*dp[p5]\n",
    "            i=min(num2,num3,num5)\n",
    "            if num2==i:\n",
    "                p2+=1\n",
    "            if num3==i:\n",
    "                p3+=1\n",
    "            if num5==i:\n",
    "                p5+=1\n",
    "            dp.append(i)\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ans = []\n",
    "        for i in range(14):\n",
    "            for j in range(21):\n",
    "                for k in range(35):\n",
    "                    a = (5 ** i )* (3 ** j )* (2 ** k)\n",
    "                    ans.append(a)\n",
    "        ans = sorted(ans)\n",
    "        return ans[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [1]\n",
    "        f = [2, 3, 5]\n",
    "        res = {1}\n",
    "        for i in range(n):\n",
    "            temp = min(dp)\n",
    "            dp.remove(temp)\n",
    "            for j in f:\n",
    "                dp.append(j*temp)\n",
    "                res.add(j*temp)\n",
    "            dp = list(set(dp))\n",
    "        res = sorted(list(res))\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ret = None\n",
    "        h = []\n",
    "        ans_set = set()\n",
    "        n2,n3,n5=0,0,0\n",
    "        heapq.heappush(h,(pow(2,n2)*pow(3,n3)*pow(5,n5),n2,n3,n5))\n",
    "        while n>0:\n",
    "            hr = heapq.heappop(h)\n",
    "            ret=hr[0]\n",
    "            if (hr[1]+1,hr[2],hr[3]) not in ans_set:\n",
    "                ans_set.add((hr[1]+1,hr[2],hr[3]))\n",
    "                heapq.heappush(h,(pow(2,hr[1]+1)*pow(3,hr[2])*pow(5,hr[3]),hr[1]+1,hr[2],hr[3]))\n",
    "            if (hr[1],hr[2]+1,hr[3]) not in ans_set:\n",
    "                ans_set.add((hr[1],hr[2]+1,hr[3]))\n",
    "                heapq.heappush(h,(pow(2,hr[1])*pow(3,hr[2]+1)*pow(5,hr[3]),hr[1],hr[2]+1,hr[3]))\n",
    "            if (hr[1],hr[2],hr[3]+1) not in ans_set:\n",
    "                ans_set.add((hr[1],hr[2],hr[3]+1))\n",
    "                heapq.heappush(h,(pow(2,hr[1])*pow(3,hr[2])*pow(5,hr[3]+1),hr[1],hr[2],hr[3]+1))\n",
    "            n-=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        res = [1]\n",
    "        a,b,c = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            temp_a,temp_b,temp_c = res[a]*2, res[b]*3, res[c]*5\n",
    "            min_val = min(temp_a,temp_b,temp_c)\n",
    "            if min_val == temp_a:\n",
    "                a += 1\n",
    "            if min_val == temp_b:\n",
    "                b += 1\n",
    "            if min_val == temp_c:\n",
    "                c += 1\n",
    "            res.append(min_val)\n",
    "        print(res)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        pointer = [0, 0, 0]\n",
    "        num = [1]\n",
    "        for _ in range(n):\n",
    "            next = [num[pointer[0]] * 2, num[pointer[1]] * 3, num[pointer[2]] * 5]\n",
    "            ans = min(next)\n",
    "            num.append(ans)\n",
    "            for i in range(3):\n",
    "                if next[i] == ans:\n",
    "                    pointer[i] += 1\n",
    "        print(num)          \n",
    "        return num[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        dp = [0]*n\n",
    "        dp[0] = 1\n",
    "        p2,p3,p5 = 0,0,0\n",
    "        for i in range(1,n):\n",
    "            dp[i] = min(dp[p2]*2,dp[p3]*3,dp[p5]*5)\n",
    "            if dp[p2]*2 == dp[i]: \n",
    "                p2 += 1\n",
    "            if dp[p3]*3 == dp[i]: \n",
    "                p3 += 1\n",
    "            if dp[p5]*5 == dp[i]: \n",
    "                p5 += 1\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        #相当于三个有序数列（只不过这个数列可以用公式来描述）归并成一个没有重复数的有序数列\n",
    "        ab = a * b // gcd(a, b)\n",
    "        ac = a * c // gcd(a, c)\n",
    "        bc = b * c // gcd(b, c)\n",
    "        abc = ab * c // gcd(ab, c)\n",
    "\n",
    "        def cnt(x):\n",
    "            ans = 0\n",
    "            ans += x // a  + x // b + x // c\n",
    "            ans -= x // ab + x // ac + x // bc\n",
    "            ans += x // abc\n",
    "            return ans\n",
    "\n",
    "        l = n - 1\n",
    "        r = 2 * 10 ** 9 + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if cnt(m) <= n:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        #print(l)\n",
    "        return max(l // a * a, l // b * b, l // c * c)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def lcm(a, b):\n",
    "            a1, b1 = a, b\n",
    "            while b1:\n",
    "                a1, b1 = b1, a1 % b1\n",
    "            return a * b // a1\n",
    "\n",
    "        def cntUgly(n, a, b, c):\n",
    "            return n // a + n // b + n // c - n // lcm(a, b) - n // lcm(a, c) - n // lcm(b, c) + n // lcm(lcm(a, b), c)\n",
    "\n",
    "        l, r = 1, 2 * 10**9\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if cntUgly(mid, a, b, c) < n:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        \n",
    "        return r # 返回第一个cntUgly>=n的值\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "\n",
    "'''\n",
    "    题目: 1201. 丑数 III\n",
    "    链接: https://leetcode.cn/problems/ugly-number-iii/description/\n",
    "    思路: 利用二分查找 + 容斥原理\n",
    "    丑数是可以被 a 或 b 或 c 整除的正整数, 设 x 是 第 k 个 丑数\n",
    "    则 \n",
    "            aa = lcm(a, b)\n",
    "            bb = lcm(b, c)\n",
    "            cc = lcm(a, c)\n",
    "            dd = lcm(lcm(a, b), c)\n",
    "            k = x // a + x // b + x // c - x // aa - x // bb - x // cc + x // dd\n",
    "    画出图形便一目了然了\n",
    "'''\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "def gcd(a, b):\n",
    "    return a if b == 0 else gcd(b, a % b)\n",
    "def lcm(a, b):\n",
    "    return a // gcd(a, b) * b\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        l = 1\n",
    "        r = int(1e10)\n",
    "        def check(x):\n",
    "            aa = lcm(a, b)\n",
    "            bb = lcm(b, c)\n",
    "            cc = lcm(a, c)\n",
    "            dd = lcm(lcm(a, b), c)\n",
    "            cnt = x // a + x // b + x // c - x // aa - x // bb - x // cc + x // dd\n",
    "            return cnt >= n\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "        \n",
    "            \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left,right = 0,min(a,b,c)*n\n",
    "        r1,r2,r3,r = math.lcm(a,b),math.lcm(a,c),math.lcm(b,c),math.lcm(a,b,c)\n",
    "        while left+1<right:\n",
    "            mid = (left+right)//2\n",
    "            total = mid//a+mid//b+mid//c - mid//r1-mid//r2-mid//r3 + mid//r\n",
    "            if total<n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def lcm(a, b):\n",
    "            tmp = a * b\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return tmp // a\n",
    "\n",
    "        lab = lcm(a, b)\n",
    "        lac = lcm(a, c)\n",
    "        lbc = lcm(b, c)\n",
    "        labc = lcm(lab, c)\n",
    "\n",
    "        def check(m) -> int:\n",
    "            cnt1 = m // a + m // b + m // c\n",
    "            cnt2 = m // lab + m // lac + m // lbc\n",
    "            cnt3 = m // labc\n",
    "            return cnt1 - cnt2 + cnt3\n",
    "            # m // a + m // b + m // c\n",
    "            # - m // lab - m // lbc - m // lac\n",
    "            # + m // labc\n",
    "\n",
    "        l = 1\n",
    "        r = min(min(a, b, c) * n, 2 * pow(10, 9))\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m) < n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        # l -= min(l % a, l % b, l % c)\n",
    "        return l\n",
    "\n",
    "\n",
    "# from math import lcm\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "#         lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)\n",
    "#         def countugly(x):\n",
    "#             return x // a + x // b + x // c - x // lab - x // lbc - x // lac + x // labc\n",
    "#         l, r = 1, min(min(a, b, c) * n, 2 * pow(10, 9))\n",
    "#         while l < r:\n",
    "#             m = (l + r) // 2\n",
    "#             if countugly(m) < n:\n",
    "#                 l = m + 1\n",
    "#             else:\n",
    "#                 r = m\n",
    "#         return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab = math.lcm(a,b)\n",
    "        bc = math.lcm(b,c)\n",
    "        ac = math.lcm(a,c)\n",
    "        abc = math.lcm(a,b,c)\n",
    "        def check(mid):\n",
    "            cnt = mid //a + mid//b + mid//c - mid // ab -mid //bc - mid//ac+mid//abc\n",
    "            return cnt >= n\n",
    "        left = 1\n",
    "        right = 2*10**9\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "\n",
    "        def check(num):\n",
    "\n",
    "            A = num // a\n",
    "            B = num // b\n",
    "            C = num // c\n",
    "\n",
    "            AB = num // lcm(a,b)\n",
    "            AC = num // lcm(a,c)\n",
    "            BC = num // lcm(b,c)\n",
    "            \n",
    "            ABC = num // lcm(a,b,c)\n",
    "\n",
    "            return A+B+C - AB-AC-BC +ABC >= n\n",
    "        \n",
    "\n",
    "        check(4)\n",
    "        i = 1\n",
    "        j = 3 * (10 ** 9)\n",
    "\n",
    "        while i < j:\n",
    "            mid = (i + j) //2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "#         nth_ugly = 1\n",
    "#         nth_num = 0\n",
    "#         while True:\n",
    "#             if nth_ugly % a == 0 or nth_ugly % b == 0 or nth_ugly % c == 0:\n",
    "#                 nth_num += 1\n",
    "\n",
    "#             if nth_num == n:\n",
    "#                 return nth_ugly\n",
    "\n",
    "#             nth_ugly += 1\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        #三数最小公倍数=两数最小公倍数与第三个数的最小公倍数\n",
    "        def Lcm3(x,y,z):\n",
    "            a = (x*y)//gcd(x,y)  \n",
    "            return (a*z)//gcd(a,z)\n",
    "        '''\n",
    "        计算有多少个丑数小于等于x\n",
    "        + x整除a,b,c -整除ab,bc,ac最小公倍数 +整除abc最小公倍数 即为所求\n",
    "        '''\n",
    "        def uglynum(x):\n",
    "                return x//a+x//b+x//c-x//(a*b//gcd(a,b))-x//(a*c//gcd(a,c))-x//(b*c//gcd(b,c))+x//Lcm3(a,b,c)\n",
    "        '''\n",
    "        二分搜索，注意只要uglynum(mid)<n left就=mid+1 所以最后得到的left就是所求\n",
    "        例如测试用例2中  a=2,b=3,c=4\n",
    "        括号中为丑数                    1,(2),(3),(4),5,(6),7,(8)\n",
    "        小于等于它们的丑数个数分别为     0, 1 , 2 , 3 ,3, 4, 4, 5 \n",
    "        若n==4\n",
    "        如果uglynum(mid)<4 则left一定能直接取到6而不是7\n",
    "        '''\n",
    "        left=1\n",
    "        right=n*min(a,b,c)\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if uglynum(mid)<n:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd(a: int, b: int) -> int:\n",
    "    if b == 0:\n",
    "        return a\n",
    "    return gcd(b, a % b)\n",
    "\n",
    "def lcm(a: int, b: int) -> int:\n",
    "    return a * b // gcd(a, b)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        l: int = 0\n",
    "        r: int = int(2e9)\n",
    "        # 这个函数可以借助gosper‘s hack与python解包功能写一个更优雅的，但没必要\n",
    "        def check(m: int, a: int, b: int, c: int) -> int:\n",
    "            return m // a + m // b + m // c - m // lcm(a, b) - m // lcm(a, c) - m // lcm(b, c) + m // lcm(a, lcm(b, c))\n",
    "        while l < r - 1:\n",
    "            mid: int = (l + r) // 2\n",
    "            if check(mid, a, b, c) >= n:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # def gcd(x, y):\n",
    "        #     while y:\n",
    "        #         x, y = y, x % y\n",
    "        #     return x\n",
    "    \n",
    "        # def lcm(x, y):\n",
    "        #     return x * y // gcd(x, y)\n",
    "        \n",
    "        lab = lcm(a, b)\n",
    "        lac = lcm(a, c)\n",
    "        lbc = lcm(b, c)\n",
    "        labc = lcm(lab, c)\n",
    "        maxabc = max(a, b, c)\n",
    "        \n",
    "        def countLessEqual(x):\n",
    "            return x // a + x // b + x // c - x // lab - x // lac - x // lbc + x // labc\n",
    "        \n",
    "        m = countLessEqual(labc)\n",
    "        q, r = divmod(n, m)\n",
    "        hi = min(labc, r * maxabc)\n",
    "        lo = 0\n",
    "        \n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if countLessEqual(mi) < r:\n",
    "                lo = mi + 1\n",
    "            else:\n",
    "                hi = mi\n",
    "        \n",
    "        return lo + q * labc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        l=0\n",
    "        r=2*10**9+1\n",
    "        while l+1!=r:\n",
    "            m=(l+r)//2\n",
    "            x=m//a+m//b+m//c\n",
    "            y=m//lcm(a,b)+m//lcm(a,c)+m//lcm(b,c)\n",
    "            z=m//lcm(*[a,b,c])\n",
    "            if x-y+z<n:\n",
    "                l=m\n",
    "            else:\n",
    "                r=m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def Lcm3(x,y,z):\n",
    "            a = (x*y)//gcd(x,y)  \n",
    "            return (a*z)//gcd(a,z)\n",
    "\n",
    "        def check(x):\n",
    "            return x//a + x//b +x//c -x//(a*b//gcd(a,b))-x//(a*c//gcd(a,c))-x//(b*c//gcd(b,c))+x//Lcm3(a,b,c)\n",
    "        l = 1\n",
    "        r = n*min(a,b,c)\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid) < n:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)\n",
    "        # 使用二分查找来找到第 n 个丑数\n",
    "        low = 1\n",
    "        high = 2 * 10 ** 9  # 设置一个足够大的上界\n",
    "        \n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            cnt = mid // a + mid // b + mid // c - mid // lab - mid // lbc - mid // lac + mid // labc\n",
    "            if cnt < n:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "                \n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # 题目说本题结果在 [1, 2 * 10^9] 范围内\n",
    "        left, right = 1, 2e9\n",
    "        # 搜索左侧边界的二分搜索 左闭右闭 [left, right]\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if self.f(mid, a, b, c) >= n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return int(left)\n",
    "\n",
    "    def f(self, num, a, b, c):\n",
    "        \"\"\"\n",
    "        函数 f 是一个单调函数, 随着num的增加而增加\n",
    "        计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字\n",
    "        :param num:\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :param c:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        set_a = num // a\n",
    "        set_b = num // b\n",
    "        set_c = num // c\n",
    "\n",
    "        set_ab = num // lcm(a, b)\n",
    "        set_ac = num // lcm(a, c)\n",
    "        set_bc = num // lcm(c, b)\n",
    "\n",
    "        set_abc = num // lcm(lcm(a, b), c)\n",
    "        # 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C\n",
    "        return set_a + set_b + set_c - set_ac - set_ab - set_bc + set_abc\n",
    "\n",
    "\n",
    "# 求两个数的最大公约数（greatest common divisor），辗转相除法\n",
    "def gcd(a, b):\n",
    "    # 保证a>b\n",
    "    if a < b:\n",
    "        return gcd(b, a)\n",
    "\n",
    "    if b == 0:\n",
    "        return a\n",
    "\n",
    "    return gcd(b, a % b)\n",
    "\n",
    "\n",
    "# 求两个数的最小公倍数（least common multiple）\n",
    "def lcm(a, b):\n",
    "    return a * b/gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab, bc, ac, abc = lcm(a,b), lcm(b,c), lcm(a,c), lcm(a,b,c)\n",
    "        def check(m):\n",
    "            cnt = m//a + m//b + m//c - m//ab - m//bc - m//ac + m//abc\n",
    "            return cnt >= n\n",
    "        l, r = 1, 2 * 10**9 + 10\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        L1 = a // gcd(a, b) * b\n",
    "        L2 = a // gcd(a, c) * c\n",
    "        L3 = c // gcd(b, c) * b\n",
    "        LL = L1 // gcd(L1, c) * c\n",
    "        l, r = 0, 100000000000000\n",
    "        while l < r:\n",
    "            mi = (l + r) // 2\n",
    "            if mi // a + mi // b + mi // c - mi // L1 - mi // L2 - mi // L3 + mi // LL < n:\n",
    "                l = mi + 1\n",
    "            else:\n",
    "                r = mi\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "        low, high = 0, 2 * 10 ** 9\n",
    "        ab = a * b // math.gcd(a, b)\n",
    "        ac = a * c // math.gcd(a, c)\n",
    "        bc = b * c // math.gcd(b, c)\n",
    "        abc = a * bc // math.gcd(a, bc)\n",
    "        while low <= high:\n",
    "            mid = low + ((high - low) >> 1)\n",
    "            cnt = mid // a + mid // b + mid // c - mid // ab - mid // ac - mid // bc + mid // abc\n",
    "            if cnt >= n:\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        if a == 1 or b == 1 or c == 1:\n",
    "            return n\n",
    "        lab, lac, lbc = a * b // math.gcd(a, b), a * c // math.gcd(a, c), b * c // math.gcd(b, c)\n",
    "        labc = lab * c // math.gcd(lab, c)\n",
    "        def cnt(n):\n",
    "            return n // a + n // b + n // c - n // lab - n // lbc - n // lac + n // labc\n",
    "        left, right = 1, n * min([a, b, c])\n",
    "        while right > left + 1:\n",
    "            mid = (left + right) // 2\n",
    "            if cnt(mid) >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import lcm\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def uglyNumber(x):\n",
    "            cnt=x//a+x//b+x//c-x//(lcm(a,b))-x//lcm(a,c) -x//lcm(b,c) +x//lcm(lcm(a,b),c)\n",
    "            return cnt>=n\n",
    "\n",
    "\n",
    "\n",
    "        l=1\n",
    "        r=2*10**9\n",
    "        while l<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if uglyNumber(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd(a: int, b: int) -> int:\n",
    "    if b == 0:\n",
    "        return a\n",
    "    return gcd(b, a % b)\n",
    "\n",
    "def lcm(a: int, b: int) -> int:\n",
    "    return a * b // gcd(a, b)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        l: int = 1\n",
    "        r: int = int(2e9)\n",
    "        # 这个函数可以借助gosper‘s hack与python解包功能写一个更优雅的，但没必要\n",
    "        def check(m: int, a: int, b: int, c: int) -> int:\n",
    "            return m // a + m // b + m // c - m // lcm(a, b) - m // lcm(a, c) - m // lcm(b, c) + m // lcm(a, lcm(b, c))\n",
    "        while l <= r:\n",
    "            mid: int = l + (r - l) // 2\n",
    "            if check(mid, a, b, c) >= n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "        gcd_ab = (a*b)//math.gcd(a,b)\n",
    "        gcd_ac = (a*c)//math.gcd(a,c)\n",
    "        gcd_bc = (b*c)//math.gcd(b,c)\n",
    "\n",
    "        gcd_abc = (gcd_ab*c)//math.gcd(gcd_ab,c)\n",
    "        def num(x):\n",
    "            return x//a + x//b + x//c + x//gcd_abc - x//gcd_ab - x//gcd_ac - x//gcd_bc\n",
    "        left = 1\n",
    "        right = n*min(a,b,c) + 1\n",
    "        mid = (left + right)//2\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            num_1 = num(mid)\n",
    "            if num_1 < n :\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n",
    "\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab = lcm(a,b)\n",
    "        bc = lcm(b,c)\n",
    "        ac = lcm(a,c)\n",
    "        abc = lcm(a,b,c)\n",
    "        def checkugly(t):\n",
    "            return t//a + t//b + t//c - t//ab - t//ac - t//bc + t//abc >= n\n",
    "        low = 1\n",
    "        up = n*min(a,b,c)\n",
    "        while low < up - 1:\n",
    "            avg = (low + up)//2\n",
    "            if checkugly(avg):\n",
    "                up = avg\n",
    "            else:\n",
    "                low =avg\n",
    "        return low if checkugly(low) else up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab, ac, bc, abc = lcm(a, b), lcm(a, c), lcm(b, c), lcm(a, b, c)\n",
    "        l, r = min(a, b, c) - 1, min(a, b, c) * n + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if m // a + m // b + m // c - m //ab - m //ac - m // bc + m // abc >= n:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left, right = 1, 2 * (10 ** 9)\n",
    "        ab, ac, bc = a * b // gcd(a, b), a*c//gcd(a, c), b*c//gcd(b, c)\n",
    "        abc = ab * c // gcd(ab, c)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // abc + mid // a + mid // b + mid // c - mid // ab - mid // ac - mid // bc >= n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "        gcd_ab = a * b // math.gcd(a,b)\n",
    "        gcd_ac = a * c // math.gcd(a,c)\n",
    "        gcd_bc = b * c // math.gcd(b,c)\n",
    "        gcd_abc = gcd_bc * a // math.gcd(gcd_bc,a)\n",
    "\n",
    "        def num(x):\n",
    "            return x // a + x // b + x // c - x // gcd_ab - x // gcd_ac -x // gcd_bc + x // gcd_abc\n",
    "        \n",
    "        left = 1\n",
    "        right = n * min(a, b, c) +1\n",
    "        mid =(left + right) // 2\n",
    "        while left < right:\n",
    "            mid =(left + right) // 2\n",
    "            num1 = num(mid)\n",
    "            if num1 < n:\n",
    "                left = mid +1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\r\n",
    "        gcd_ab=(a*b)//math.gcd(a,b)\r\n",
    "        gcd_ac=(a*c)//math.gcd(a,c)\r\n",
    "        gcd_bc=(b*c)//math.gcd(b,c)\r\n",
    "        gcd_abc=(gcd_bc*a)//math.gcd(gcd_bc,a)\r\n",
    "        def num(x):\r\n",
    "            return x//a+x//b+x//c-x//gcd_ab-x//gcd_ac-x//gcd_bc+x//gcd_abc\r\n",
    "        left=1\r\n",
    "        right=n*min(a,b,c)+1\r\n",
    "        mid=(left+right)//2\r\n",
    "        while left<right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "            num_1=num(mid)\r\n",
    "            if num_1<n:\r\n",
    "                left=mid+1\r\n",
    "            else:\r\n",
    "                right=mid\r\n",
    "        return right\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # def isUglyNumber(k):\n",
    "        #     if k % a == 0 or k % b == 0 or k % c == 0:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # min_value = min(a, min(b, c))\n",
    "        # lst = []\n",
    "        # i = a\n",
    "        # while len(lst) <= n:\n",
    "        #     if isUglyNumber(i):\n",
    "        #         lst.append(i)\n",
    "        #     i += 1\n",
    "        # print(lst)\n",
    "        # return lst[n-1]\n",
    "        ab = math.lcm(a, b)\n",
    "        ac = math.lcm(a, c)\n",
    "        bc = math.lcm(c, b)\n",
    "        abc = math.lcm(a, b, c)\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            cnt += num//a\n",
    "            cnt += num//b\n",
    "            cnt += num//c\n",
    "            cnt -= num//ab\n",
    "            cnt -= num //ac\n",
    "            cnt -= num//bc\n",
    "            cnt += num//abc\n",
    "            return cnt \n",
    "        left = 1\n",
    "        right = min(a, b, c) * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        #三数最小公倍数=两数最小公倍数与第三个数的最小公倍数\n",
    "        def Lcm3(x,y,z):\n",
    "            a = (x*y)//gcd(x,y)  \n",
    "            return (a*z)//gcd(a,z)\n",
    "        '''\n",
    "        计算有多少个丑数小于等于x\n",
    "        + x整除a,b,c -整除ab,bc,ac最小公倍数 +整除abc最小公倍数 即为所求\n",
    "        '''\n",
    "        def uglynum(x):\n",
    "                return x//a+x//b+x//c-x//(a*b//gcd(a,b))-x//(a*c//gcd(a,c))-x//(b*c//gcd(b,c))+x//Lcm3(a,b,c)\n",
    "        '''\n",
    "        二分搜索，注意只要uglynum(mid)<n left就=mid+1 所以最后得到的left就是所求\n",
    "        例如测试用例2中  a=2,b=3,c=4\n",
    "        括号中为丑数                    1,(2),(3),(4),5,(6),7,(8)\n",
    "        小于等于它们的丑数个数分别为     0, 1 , 2 , 3 ,3, 4, 4, 5 \n",
    "        若n==4\n",
    "        如果uglynum(mid)<4 则left一定能直接取到6而不是7\n",
    "        '''\n",
    "        left=1\n",
    "        right=n*min(a,b,c)\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if uglynum(mid)<n:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left, right = 1, min(a, b, c) * n\n",
    "        ab, ac, bc = a * b // gcd(a, b), a*c//gcd(a, c), b*c//gcd(b, c)\n",
    "        abc = ab * c // gcd(ab, c)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid // abc + mid // a + mid // b + mid // c - mid // ab - mid // ac - mid // bc >= n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)\n",
    "        # 使用二分查找来找到第 n 个丑数\n",
    "        low = 0\n",
    "        high = 2 * 10 ** 9 + 1  # 设置一个足够大的上界\n",
    "        \n",
    "        while low  + 1< high:\n",
    "            mid = (low + high) // 2\n",
    "            cnt = mid // a + mid // b + mid // c - mid // lab - mid // lbc - mid // lac + mid // labc\n",
    "            if cnt < n:\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "                \n",
    "        return high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def enough(num):\n",
    "            total = mid // a + mid // b + mid // c - mid //ab - mid // ac - mid // bc + mid //abc\n",
    "            return total >= n\n",
    "        ab = a * b // math.gcd(a,b)\n",
    "        ac = a * c // math.gcd(a,c)\n",
    "        bc = b * c // math.gcd(b,c)\n",
    "        abc = a * bc // math.gcd(a,bc)\n",
    "        l, r = 0, 10 ** 10\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if enough(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(x: int, y: int) -> int:\n",
    "            if x < y:\n",
    "                # 保证 x > y\n",
    "                return gcd(y, x)\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "\n",
    "        def lcm(x: int, y: int) -> int:\n",
    "            # 最小公倍数就是乘积除以最大公因数\n",
    "            return x * y // gcd(x, y)\n",
    "\n",
    "        # 题目说本题结果在 [1, 2 * 10^9] 范围内，\n",
    "        # 所以就按照这个范围初始化两端都闭的搜索区间\n",
    "        left, right = 1, 2 * 10 ** 9\n",
    "        # 搜索左侧边界的二分搜索\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if (mid // a + mid // b + mid // c -\n",
    "               mid // lcm(a, b) - mid // lcm(b, c) -\n",
    "               mid // lcm(a, c) + mid // lcm(lcm(a, b), c)) < n:\n",
    "                # [1..mid] 中的元素个数不足 n，所以目标在右侧\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                # [1..mid] 中的元素个数大于 n，所以目标在左侧\n",
    "                right = mid - 1\n",
    "        return left\n",
    "# 详细解析参见：\n",
    "# https://labuladong.gitee.io/article/?qno=\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "        l, r = 0, min(a, b, c) * n\n",
    "        \n",
    "        def check(x):\n",
    "            \n",
    "            tot = (x // a + x // b + x // c - x // lcm(a, b) - x // lcm(a, c) - x // lcm(b, c) + \n",
    "            x // lcm(a, b, c))\n",
    "            return tot >= n\n",
    "\n",
    "        ans = -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        \n",
    "        def lcm2(a, b):\n",
    "            return a * b // math.gcd(a, b) \n",
    "        def lcm3(a, b, c):\n",
    "            x = lcm2(a,b)\n",
    "            return x * c // math.gcd(x, c)\n",
    "            #return lcm2(lcm2(a,b), c)\n",
    "\n",
    "        def check(k):\n",
    "            y = k // a + k // b + k // c - k // lcm2(a,b) - k // lcm2(a,c) - k // lcm2(b,c) + k // lcm3(a, b, c)\n",
    "            return y >= n\n",
    "        \n",
    "        l, r = 1, int(2e9)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "        a1=math.lcm(a,b)\n",
    "        a2=math.lcm(a,c)\n",
    "        a3=math.lcm(b,c)\n",
    "        a4=math.lcm(a,b,c)\n",
    "        def check(t):\n",
    "            return (t//a+t//b+t//c-t//a1-t//a2-t//a3+t//a4)>=n\n",
    "        cmin=1\n",
    "        cmax=min(2*(10**9),min(a,b,c)*n)\n",
    "        \n",
    "        while cmin<=cmax:\n",
    "            mid=(cmin+cmax)//2\n",
    "            if check(mid):\n",
    "                cur=mid\n",
    "                cmax=mid-1\n",
    "            else:\n",
    "                cmin=mid+1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab=math.lcm(a,b)\n",
    "        ac=math.lcm(a,c)\n",
    "        bc=math.lcm(b,c)\n",
    "        abc=math.lcm(a,b,c)\n",
    "        def check(x):\n",
    "            cnt=0\n",
    "            cnt+=x//a\n",
    "            cnt+=x//b\n",
    "            cnt+=x//c\n",
    "            cnt-=x//ab\n",
    "            cnt-=x//ac\n",
    "            cnt-=x//bc\n",
    "            cnt+=x//abc\n",
    "            return cnt>=n\n",
    "        l,r=0,min(a,b,c)*(n+1)\n",
    "        while l+1<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        return l if check(l) else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(x: int, y: int) -> int:\n",
    "            if x < y:\n",
    "                # 保证 x > y\n",
    "                return gcd(y, x)\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "\n",
    "        def lcm(x: int, y: int) -> int:\n",
    "            # 最小公倍数就是乘积除以最大公因数\n",
    "            return x * y // gcd(x, y)\n",
    "\n",
    "        # 题目说本题结果在 [1, 2 * 10^9] 范围内，\n",
    "        # 所以就按照这个范围初始化两端都闭的搜索区间\n",
    "        left, right = 0, 2 * 10 ** 9\n",
    "        # 搜索左侧边界的二分搜索\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if (mid // a + mid // b + mid // c -\n",
    "               mid // lcm(a, b) - mid // lcm(b, c) -\n",
    "               mid // lcm(a, c) + mid // lcm(lcm(a, b), c)) < n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        # print(left, right)\n",
    " \n",
    "        if (left // a + left // b + left // c -\n",
    "               left // lcm(a, b) - left // lcm(b, c) -\n",
    "               left // lcm(a, c) + left // lcm(lcm(a, b), c)) > n:\n",
    "            return left\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        \n",
    "        ab = math.lcm(a, b)\n",
    "        ac = math.lcm(a, c)\n",
    "        bc = math.lcm(c, b)\n",
    "        abc = math.lcm(a, b, c)\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            cnt += num//a\n",
    "            cnt += num//b\n",
    "            cnt += num//c\n",
    "            cnt -= num//ab\n",
    "            cnt -= num //ac\n",
    "            cnt -= num//bc\n",
    "            cnt += num//abc\n",
    "            return cnt\n",
    "        left,right = 1,n*min(a,b,c)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid)<n:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        \n",
    "        ab = math.lcm(a, b)\n",
    "        ac = math.lcm(a, c)\n",
    "        bc = math.lcm(c, b)\n",
    "        abc = math.lcm(a, b, c)\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            cnt += num // a\n",
    "            cnt += num // b\n",
    "            cnt += num // c\n",
    "            cnt -= num // ab\n",
    "            cnt -= num // ac\n",
    "            cnt -= num // bc\n",
    "            cnt += num // abc\n",
    "            return cnt >= n\n",
    "\n",
    "\n",
    "        low = 1\n",
    "        high = 2*10**9\n",
    "        while low < high-1:\n",
    "            mid = (low+high)//2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "\n",
    "        return low if check(low) else high\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        import math\n",
    "        gcd_ab = a * b // math.gcd(a,b)\n",
    "        gcd_ac = a * c // math.gcd(a,c)\n",
    "        gcd_bc = b * c // math.gcd(b,c)\n",
    "        gcd_abc = gcd_bc * a // math.gcd(gcd_bc,a)\n",
    "\n",
    "        def num(x):\n",
    "            return x // a + x // b + x // c - x // gcd_ab - x // gcd_ac -x // gcd_bc + x // gcd_abc\n",
    "        \n",
    "        left = 1\n",
    "        right = n * min(a, b, c) + 1\n",
    "        #mid = (left + right) // 2\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            num1 = num(mid)\n",
    "            if num1 < n:\n",
    "                left = mid +1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left, right = 1, n*min(a,b,c)\n",
    "        if a == 1 or b == 1 or c == 1:return n\n",
    "        def lcm3(x,y,z):\n",
    "            a = x*y//gcd(x,y)\n",
    "            return a*z//gcd(a,z)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            cnt = mid//a + mid//b + mid//c - mid//(a*b//gcd(a,b)) - mid//(a*c//gcd(a,c)) - mid//(b*c//gcd(b,c))+ mid//lcm3(a,b,c)\n",
    "\n",
    "            if cnt < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "            \n",
    "        \n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left, right = min(a, b, c), min(a * n, b * n, c * n)\n",
    "        x, y, z = a * b // gcd(a, b), b * c // gcd(b, c), a * c // gcd(a, c)\n",
    "        ccc = x * y // gcd(x, y)\n",
    "        # print(x, y, z, ccc)\n",
    "        def get(limit, x):\n",
    "            cnt = limit // x\n",
    "            return cnt\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # print(mid)\n",
    "            if get(mid, a) + get(mid, b) + get(mid, c) - get(mid, x) - get(mid, y) - get(mid, z) + get(mid, ccc) >= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def check(m):\n",
    "            ab, bc, ac, abc = lcm(a,b), lcm(b,c), lcm(a,c), lcm(a,b,c)\n",
    "            cnt = m//a + m//b + m//c - m//ab - m//bc - m//ac + m//abc\n",
    "            return cnt >= n\n",
    "        l, r = 1, 2 * 10**9 + 10\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import lcm\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab, bc, ac, abc = lcm(a,b),lcm(b,c),lcm(a,c),lcm(a,b,c)\n",
    "        def check(lmt):\n",
    "            rnt=lmt//a+lmt//b+lmt//c-lmt//ab-lmt//bc-lmt//ac+lmt//abc\n",
    "            return rnt>=n\n",
    "        return bisect_left(range(10**10),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "        # 最小公倍数\n",
    "        lcm_ab, lcm_ac, lcm_bc = (a * b) // gcd(a, b), (a * c) // gcd(a, c), (b * c) // gcd(b, c)\n",
    "        lcm_abc = (lcm_ab * lcm_ac) // gcd(lcm_ab, lcm_ac)\n",
    "        # 通分的系数\n",
    "        a_f, b_f, c_f = lcm_abc // a, lcm_abc // b, lcm_abc // c\n",
    "        ab_f, ac_f, bc_f = lcm_abc // lcm_ab, lcm_abc // lcm_ac, lcm_abc // lcm_bc\n",
    "        x = n * lcm_abc // (a_f + b_f + c_f - ab_f - ac_f - bc_f + 1)\n",
    "        m = x // a + x // b + x // c - x // lcm_ab - x // lcm_ac - x // lcm_bc + x // lcm_abc\n",
    "\n",
    "        if m < n:\n",
    "            x += min(a - x % a, b - x % b, c - x % c)\n",
    "        else:\n",
    "            x -= min(x % a, x % b, x % c)\n",
    "            if m - n > 0:\n",
    "                x -= min(x % a or a, x % b or b, x % c or c)\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab = math.lcm(a,b)\n",
    "        ac = math.lcm(a,c)\n",
    "        bc = math.lcm(b,c)\n",
    "        abc = math.lcm(a,b,c)\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            cnt=num//a + num//b  + num//c- num//ab-num//ac-num//bc  + num//abc \n",
    "            return cnt \n",
    "        low = 1 \n",
    "        high = 2*10**9\n",
    "        while(low<high):\n",
    "            mid  = (low+high)//2 \n",
    "            if check(mid)<n:\n",
    "                low = mid +1 \n",
    "            else:\n",
    "                high = mid \n",
    "        return low\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "        lab = lcm(a,b)\n",
    "        lac = lcm(a,c)\n",
    "        lbc = lcm(b,c)\n",
    "        labc = lcm(a,b,c)\n",
    "\n",
    "        def check(num):\n",
    "\n",
    "            A = num // a\n",
    "            B = num // b\n",
    "            C = num // c\n",
    "\n",
    "            AB = num // lab\n",
    "            AC = num // lac\n",
    "            BC = num // lbc\n",
    "            \n",
    "            ABC = num // labc\n",
    "\n",
    "            return A+B+C - AB-AC-BC +ABC >= n\n",
    "        \n",
    "\n",
    "        check(4)\n",
    "        i = 1\n",
    "        j = 2 * (10 ** 9) + 100\n",
    "\n",
    "        while i < j:\n",
    "            mid = (i + j) //2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "#         # def gcd(a, b):\n",
    "#         #     return a if b == 0 else gcd(b, a % b)\n",
    "#         def lcm(a, b):\n",
    "#             tmp = a * b\n",
    "#             while b:\n",
    "#                 a, b = b, a % b\n",
    "#             return tmp // a\n",
    "\n",
    "#         def check(m) -> int:\n",
    "#             cnt1 = m // a + m // b + m // c\n",
    "#             cnt2 = m // lAB + m // lAC + m // lBC\n",
    "#             cnt3 = lABC\n",
    "#             return cnt1 - cnt2 + cnt3\n",
    "\n",
    "#         lAB = lcm(a, b)\n",
    "#         lAC = lcm(a, c)\n",
    "#         lBC = lcm(b, c)\n",
    "#         lABC = lcm(lAB, c)\n",
    "#         l = min(a, b, c)\n",
    "#         r = l * n\n",
    "\n",
    "#         while l < r:\n",
    "#             m = (l + r) // 2\n",
    "#             cnt = check(m)\n",
    "#             if cnt < n:\n",
    "#                 l = m + 1\n",
    "#             else:\n",
    "#                 r = m\n",
    "\n",
    "#         l -= min(l % a, l % b, l % c)\n",
    "#         return l\n",
    "\n",
    "# def lcm(a, b):\n",
    "#     tmp = a * b\n",
    "#     while b:\n",
    "#         a, b = b, a % b\n",
    "#     return tmp // a\n",
    "from math import lcm\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)\n",
    "\n",
    "        def countugly(x):\n",
    "            return x // a + x // b + x // c - x // lab - x // lbc - x // lac + x // labc\n",
    "\n",
    "        l, r = 1, min(min(a, b, c) * n, 2 * pow(10, 9))\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if countugly(m) < n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # 题目说本题结果在 [1, 2 * 10^9] 范围内\n",
    "        left, right = 1, 2e9\n",
    "        # 搜索左侧边界的二分搜索 左闭右闭 [left, right]\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if self.f(mid, a, b, c) >= n:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return int(left)\n",
    "\n",
    "    def f(self, num, a, b, c):\n",
    "        \"\"\"\n",
    "        函数 f 是一个单调函数, 随着num的增加而增加\n",
    "        计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字\n",
    "        :param num:\n",
    "        :param a:\n",
    "        :param b:\n",
    "        :param c:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        set_a = num // a\n",
    "        set_b = num // b\n",
    "        set_c = num // c\n",
    "\n",
    "        set_ab = num // lcm(a, b)\n",
    "        set_ac = num // lcm(a, c)\n",
    "        set_bc = num // lcm(c, b)\n",
    "\n",
    "        set_abc = num // lcm(lcm(a, b), c)\n",
    "        # 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C\n",
    "        return set_a + set_b + set_c - set_ac - set_ab - set_bc + set_abc\n",
    "\n",
    "\n",
    "# 求两个数的最大公约数（greatest common divisor），辗转相除法\n",
    "def gcd(a, b):\n",
    "    # 保证a>b\n",
    "    if a < b:\n",
    "        return gcd(b, a)\n",
    "\n",
    "    if b == 0:\n",
    "        return a\n",
    "\n",
    "    return gcd(b, a % b)\n",
    "\n",
    "\n",
    "# 求两个数的最小公倍数（least common multiple）\n",
    "def lcm(a, b):\n",
    "    return a * b/gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        #相当于三个有序数列（只不过这个数列可以用公式来描述）归并成一个没有重复数的有序数列\n",
    "        ab = a * b // gcd(a, b)\n",
    "        ac = a * c // gcd(a, c)\n",
    "        bc = b * c // gcd(b, c)\n",
    "        abc = ab * c // gcd(ab, c)\n",
    "\n",
    "        def cnt(x):\n",
    "            ans = 0\n",
    "            ans += x // a  + x // b + x // c\n",
    "            ans -= x // ab + x // ac + x // bc\n",
    "            ans += x // abc\n",
    "            return ans\n",
    "\n",
    "        l = n - 1\n",
    "        r = 2 * 10 ** 9 + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if cnt(m) <= n:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "\n",
    "        return max(l // a * a, l // b * b, l // c * c)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab=math.lcm(a,b)\n",
    "        ac=math.lcm(a,c)\n",
    "        bc=math.lcm(b,c)\n",
    "        abc=math.lcm(a,b,c)\n",
    "        def check(x):\n",
    "            cnt=0\n",
    "            cnt+=x//a\n",
    "            cnt+=x//b\n",
    "            cnt+=x//c\n",
    "            cnt-=x//ab\n",
    "            cnt-=x//ac\n",
    "            cnt-=x//bc\n",
    "            cnt+=x//abc\n",
    "            return cnt>=n\n",
    "        l,r=0,min(a,b,c)*(n+1)\n",
    "        while l+1<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        return l if check(l) else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\r\n",
    "        gcd_ab = math.lcm(a, b)\r\n",
    "        gcd_ac = math.lcm(a, c)\r\n",
    "        gcd_bc = math.lcm(b, c)\r\n",
    "        gcd_abc = math.lcm(a, b, c)\r\n",
    "        def num(x):\r\n",
    "            return x // a + x // b + x // c - x // gcd_ab - x // gcd_ac - x // gcd_bc + x // gcd_abc\r\n",
    "        left = 1\r\n",
    "        right = n * min(a,b,c) + 1\r\n",
    "        mid = (left + right) // 2\r\n",
    "        while(left < right):\r\n",
    "            mid = (left + right) // 2\r\n",
    "            num_1 = num(mid)\r\n",
    "            if num_1 < n:\r\n",
    "                left = mid + 1\r\n",
    "            else:\r\n",
    "                right = mid\r\n",
    "        return(right)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "        lab = lcm(a,b)\n",
    "        lac = lcm(a,c)\n",
    "        lbc = lcm(b,c)\n",
    "        labc = lcm(a,b,c)\n",
    "\n",
    "        def check(num):\n",
    "\n",
    "            A = num // a\n",
    "            B = num // b\n",
    "            C = num // c\n",
    "\n",
    "            AB = num // lab\n",
    "            AC = num // lac\n",
    "            BC = num // lbc\n",
    "            \n",
    "            ABC = num // labc\n",
    "\n",
    "            return A+B+C - AB-AC-BC +ABC >= n\n",
    "        \n",
    "\n",
    "        check(4)\n",
    "        i = 1\n",
    "        j = 3 * (10 ** 9)\n",
    "\n",
    "        while i < j:\n",
    "            mid = (i + j) //2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # def gcd(a, b):\n",
    "        #     return a if b == 0 else gcd(b, a % b)\n",
    "        def lcm(a, b):\n",
    "            tmp = a * b\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return tmp // a\n",
    "\n",
    "        def check(m) -> int:\n",
    "            cnt1 = m // a + m // b + m // c\n",
    "            cnt2 = m // lAB + m // lAC + m // lBC\n",
    "            cnt3 = m // lABC\n",
    "            return cnt1 - cnt2 + cnt3\n",
    "\n",
    "        lAB = lcm(a, b)\n",
    "        lAC = lcm(a, c)\n",
    "        lBC = lcm(b, c)\n",
    "        lABC = lcm(lAB, c)\n",
    "        l = min(a, b, c)\n",
    "        r = l * n\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            cnt = check(m)\n",
    "            if cnt < n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        l -= min(l % a, l % b, l % c)\n",
    "        return l\n",
    "\n",
    "\n",
    "# from math import lcm\n",
    "# class Solution:\n",
    "#     def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "#         lab, lbc, lac, labc = lcm(a, b), lcm(b, c), lcm(a, c), lcm(a, b, c)\n",
    "#         def countugly(x):\n",
    "#             return x // a + x // b + x // c - x // lab - x // lbc - x // lac + x // labc\n",
    "#         l, r = 1, min(min(a, b, c) * n, 2 * pow(10, 9))\n",
    "#         while l < r:\n",
    "#             m = (l + r) // 2\n",
    "#             if countugly(m) < n:\n",
    "#                 l = m + 1\n",
    "#             else:\n",
    "#                 r = m\n",
    "#         return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def lcm1(a,b,c):\n",
    "            gcd1 = gcd(a,b)\n",
    "            lcm1 = a*b//gcd1\n",
    "            gcd2 = gcd(c, lcm1)\n",
    "            return c*lcm1//gcd2\n",
    "        l = min([a,b,c])\n",
    "        r = n*l\n",
    "        ans = l\n",
    "        while l<=r:\n",
    "            m = (r+l)//2\n",
    "            if m//a+m//b+m//c-m//lcm(a,b)-m//lcm(a,c)-m//lcm(b,c)+m//lcm1(a,b,c)<n:\n",
    "                l = m+1\n",
    "            else:\n",
    "                ans = m\n",
    "                r = m-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "def I():\n",
    "    return input()\n",
    "\n",
    "def II():\n",
    "    return int(input())\n",
    " \n",
    "def MII():\n",
    "    return map(int, input().split())\n",
    " \n",
    "def LI():\n",
    "    return list(input().split())\n",
    " \n",
    "def LII():\n",
    "    return list(map(int, input().split()))\n",
    " \n",
    "def GMI():\n",
    "    return map(lambda x: int(x) - 1, input().split())\n",
    " \n",
    "def LGMI():\n",
    "    return list(map(lambda x: int(x) - 1, input().split()))\n",
    "# start-----------------------------------------------------\n",
    "def gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a\n",
    "    else:\n",
    "        return gcd(b, a % b)\n",
    "def lcm(a, b):\n",
    "    return a // gcd(a, b) * b\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        l = 1\n",
    "        r = int(1e10)\n",
    "        def check(x):\n",
    "            aa = lcm(a, b)\n",
    "            bb = lcm(b, c)\n",
    "            cc = lcm(a, c)\n",
    "            dd = lcm(a, b)\n",
    "            dd = lcm(dd, c)\n",
    "            cnt = x // a + x // b + x // c - x // aa - x // bb - x // cc + x // dd\n",
    "            return cnt >= n\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "        \n",
    "            \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            if (b):\n",
    "                return gcd(b, a % b)\n",
    "            else:\n",
    "                return a\n",
    "        def lcm(a,b):\n",
    "            return int(a*b//gcd(a,b))\n",
    "        def cnt(mid, a, b, c):\n",
    "            ab = int(lcm(a,b))\n",
    "            ac = int(lcm(a,c))\n",
    "            bc = int(lcm(b,c))\n",
    "            abc = int(lcm(a,lcm(b,c)))\n",
    "            return int(mid / a) + int(mid / b) + int(mid / c) - int(mid / ab) - int(mid / ac) - int(mid / bc) + int(mid /abc)\n",
    "        head = min(a,min(b,c))\n",
    "        tail = n* min(a, min(b,c))\n",
    "        while head <= tail:\n",
    "             mid = int((head + tail)//2)\n",
    "             if cnt(mid, a, b, c) == n:\n",
    "                 tail = mid - 1\n",
    "             elif cnt(mid, a, b, c) < n:\n",
    "                head = mid + 1\n",
    "             else:\n",
    "                 tail = mid - 1\n",
    "        return head   \n",
    "\n",
    "            \n",
    "            \n",
    "                \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        def lcm(a, b):\n",
    "            return a*b//gcd(a,b)\n",
    "        def lcm1(a,b,c):\n",
    "            gcd1 = gcd(a,b)\n",
    "            lcm1 = a*b//gcd1\n",
    "            gcd2 = gcd(c, lcm1)\n",
    "            return c*lcm1//gcd2\n",
    "        l = min([a,b,c])\n",
    "        r = n*l\n",
    "        ans = l\n",
    "        while l<=r:\n",
    "            m = (r+l)//2\n",
    "            if m//a+m//b+m//c-m//lcm(a,b)-m//lcm(a,c)-m//lcm(b,c)+m//lcm1(a,b,c)<n:\n",
    "                l = m+1\n",
    "            else:\n",
    "                ans = m\n",
    "                r = m-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def lcm3(x, y, z):\n",
    "            a = (x*y)//gcd(x,y)\n",
    "            return (a*z)//gcd(a,z)\n",
    "        \n",
    "        def uglynum(x):\n",
    "            return x//a+x//b+x//c-x//(a*b//gcd(a,b))-x//(b*c//gcd(b,c))-x//(a*c//gcd(a,c)) + x//lcm3(a,b,c)\n",
    "        \n",
    "        left = 1\n",
    "        right = n*min(a, b, c)\n",
    "        while left < right:\n",
    "            mid = (left+right) >> 1\n",
    "            if uglynum(mid) < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        gcd_ab=(a*b)//math.gcd(a,b)\n",
    "        gcd_ac=(a*c)//math.gcd(a,c)\n",
    "        gcd_bc=(b*c)//math.gcd(b,c)\n",
    "        gcd_abc=(gcd_bc*a)//math.gcd(gcd_bc,a)\n",
    "        def check(x):\n",
    "            return x//a+x//b+x//c-x//gcd_ab-x//gcd_ac-x//gcd_bc+x//gcd_abc\n",
    "\n",
    "        left=1\n",
    "        right=2*10**9\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid)<n:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab = math.lcm(a,b)\n",
    "        bc = math.lcm(b,c)\n",
    "        ac = math.lcm(a,c)\n",
    "        abc = math.lcm(a,b,c)\n",
    "        def check(num):\n",
    "            res = 0\n",
    "            res += num//a + num//b + num//c - num//ab - num//bc - num//ac + num//abc \n",
    "            return res>=n \n",
    "        left = 1 \n",
    "        right = min(a,b,c)*n \n",
    "        while left<=right:\n",
    "            mid = (left+right)//2 \n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if check(left):\n",
    "            return left\n",
    "        else:\n",
    "            return right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab = math.lcm(a, b)\n",
    "        ac = math.lcm(a, c)\n",
    "        bc = math.lcm(c, b)\n",
    "        abc = math.lcm(a, b, c)\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            cnt += num//a\n",
    "            cnt += num//b\n",
    "            cnt += num//c\n",
    "            cnt -= num//ab\n",
    "            cnt -= num //ac\n",
    "            cnt -= num//bc\n",
    "            cnt += num//abc\n",
    "            return cnt >= n\n",
    "        low = 1\n",
    "        high = 2*10**9\n",
    "        while low < high-1:\n",
    "            mid = low+(high-low)//2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            return a if b==0 else gcd(b,a%b)\n",
    "        def lcm(a,b):\n",
    "            return a*b/gcd(a,b)\n",
    "        def hanshu(s):\n",
    "            return s//a+s//b+s/c-s//lcm(a,b)-s//lcm(a,c)-s//lcm(b,c)+s//lcm(c,lcm(a,b))\n",
    "        l,r = 1,2*10**9+1\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if hanshu(m) < n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n",
    "        # return bisect_right(range(1,2*10^9+1),n,key = hanshu)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            if b == 0:\n",
    "                return a\n",
    "            return gcd(b, a%b)\n",
    "        def lcm(a, b):\n",
    "            return (a*b)//gcd(a,b)\n",
    "        \n",
    "        def f(x, a, b, c):\n",
    "            num = x//a+x//b+x//c-x//lcm(a,b)-x//lcm(a,c)-x//lcm(b,c)+x//lcm(a,lcm(b,c))\n",
    "            return num\n",
    "        \n",
    "        left = 1\n",
    "        right = 2*10**9\n",
    "        while left <= right:\n",
    "            mid = (left + right) //2\n",
    "            if n>f(mid, a, b,c):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        left, right = 0, 2 * 10 ** 9\n",
    "\n",
    "        v1 = (a * b) // math.gcd(a, b)\n",
    "        v2 = (b * c) // math.gcd(b, c)\n",
    "        v3 = (a * c) // math.gcd(a, c)\n",
    "        v4 = (v1 * c) // math.gcd(v1, c)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            n1 = mid // a\n",
    "            n2 = mid // b\n",
    "            n3 = mid // c\n",
    "            n4 = mid // v1\n",
    "            n5 = mid // v2\n",
    "            n6 = mid // v3\n",
    "            n7 = mid // v4\n",
    "            num = n1 + n2 + n3 - n4 - n5 - n6 + n7\n",
    "\n",
    "            if num < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            return gcd(b, a%b) if b else a\n",
    "        def lcm(a,b):\n",
    "            return a*b//gcd(a,b)\n",
    "        ab = lcm(a,b)\n",
    "        ac = lcm(a,c)\n",
    "        bc = lcm(b,c)\n",
    "        abc = lcm(ab,bc)\n",
    "        maxnum = max(a,b,c) * n\n",
    "        l,r = 0,maxnum\n",
    "        def cal(num):\n",
    "            nonlocal a,b,c,ab,bc,ac,abc\n",
    "            return num//a + num//b + num//c - num//ab - num//ac - num//bc + num//abc\n",
    "        res = 0\n",
    "        while l<=r:\n",
    "            mid = l + (r-l)//2\n",
    "            if cal(mid) >= n:\n",
    "                res = mid\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "这道题和之前题目的不同之处在于它改变了「丑数」的定义，只要一个正整数x存在a, b, c中的任何一个因子，那么x就是丑数。\n",
    "\n",
    "有了之前几道题的铺垫，你肯定可以想到把a, b, c的倍数抽象成三条有序链表：\n",
    "\n",
    "1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 7*3 ->...\n",
    "1*4 -> 2*4 -> 3*4 -> 4*4 -> 5*4 -> 6*4 -> 7*4 ->...\n",
    "1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 7*5 ->...\n",
    "\n",
    "    // 可以理解为三个有序链表的头结点的值\n",
    "    // 由于数据规模较大，用 long 类型\n",
    "    long productA = a, productB = b, productC = c;\n",
    "    // 可以理解为合并之后的有序链表上的指针\n",
    "    int p = 1;\n",
    "\n",
    "    long min = -666;\n",
    "\n",
    "    // 开始合并三个有序链表，获取第 n 个节点的值\n",
    "    while (p <= n) {\n",
    "        // 取三个链表的最小结点\n",
    "        min = Math.min(Math.min(productA, productB), productC);\n",
    "        p++;\n",
    "        // 前进最小结点对应链表的指针\n",
    "        if (min == productA) {\n",
    "            productA += a;\n",
    "        }\n",
    "        if (min == productB) {\n",
    "            productB += b;\n",
    "        }\n",
    "        if (min == productC) {\n",
    "            productC += c;\n",
    "        }\n",
    "    }\n",
    "    return (int) min;\n",
    "}\n",
    "\n",
    "注意题目给的数据范围非常大，a, b, c, n的大小可以达到 10^9，所以即便上述算法的时间复杂度是O(n)，\n",
    "也是相对比较耗时的，应该有更好的思路能够进一步降低时间复杂度。\n",
    "\n",
    "这道题的正确解法难度比较大，难点在于你要把一些数学知识和 二分搜索技巧 结合起来才能高效解决这个问题。\n",
    "\n",
    "首先，我们可以定义一个单调递增的函数f：\n",
    "\n",
    "f(num, a, b, c)计算[1..num]中，能够整除a或b或c的数字的个数，显然函数f的返回值是随着num的增加而增加的（单调递增）。\n",
    "\n",
    "题目让我们求第n个能够整除a或b或c的数字是什么，也就是说我们要找到一个最小的num，使得f(num, a, b, c) == n。\n",
    "\n",
    "这个num就是第n个能够整除a或b或c的数字。\n",
    "\n",
    "根据 二分查找的实际运用 给出的思路模板，我们得到一个单调函数f，想求参数num的最小值，就可以运用搜索左侧边界的二分查找算法了：\n",
    "\n",
    "int nthUglyNumber(int n, int a, int b, int c) {\n",
    "    // 题目说本题结果在 [1, 2 * 10^9] 范围内，\n",
    "    // 所以就按照这个范围初始化两端都闭的搜索区间\n",
    "    int left = 1, right = (int) 2e9;\n",
    "    // 搜索左侧边界的二分搜索\n",
    "    while (left <= right) {\n",
    "        int mid = left + (right - left) / 2;\n",
    "        if (f(mid, a, b, c) < n) {\n",
    "            // [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边\n",
    "            left = mid + 1;\n",
    "        } else {\n",
    "            // [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边\n",
    "            right = mid - 1;\n",
    "        }\n",
    "    }\n",
    "    return left;\n",
    "}\n",
    "\n",
    "// 函数 f 是一个单调函数\n",
    "// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字\n",
    "long f(int num, int a, int b, int c) {\n",
    "    // 下文实现\n",
    "}\n",
    "\n",
    "搜索左侧边界的二分搜索代码模板在 二分查找框架详解 中讲过，没啥可说的，关键说一下函数f怎么实现，\n",
    "这里面涉及容斥原理以及最小公因数、最小公倍数的计算方法。\n",
    "\n",
    "首先，我把[1..num]中能够整除a的数字归为集合A，能够整除b的数字归为集合B，能够整除c的数字归为集合C，\n",
    "那么len(A) = num / a, len(B) = num / b, len(C) = num / c，这个很好理解。\n",
    "\n",
    "但是f(num, a, b, c)的值肯定不是num / a + num / b + num / c这么简单，\n",
    "因为你注意有些数字可能可以被a, b, c中的两个数或三个数同时整除，如下图：\n",
    "\n",
    "\n",
    "按照容斥原理，这个集合中的元素应该是：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C。结合上图应该很好理解。\n",
    "\n",
    "问题来了，A, B, C三个集合的元素个数我们已经算出来了，但如何计算像A ∩ B这种交集的元素个数呢？\n",
    "\n",
    "其实也很容易想明白，A ∩ B的元素个数就是num / lcm(a, b)，其中lcm是计算最小公倍数（Least Common Multiple）的函数。\n",
    "\n",
    "类似的，A ∩ B ∩ C的元素个数就是num / lcm(lcm(a, b), c)的值。\n",
    "\n",
    "现在的问题是，最小公倍数怎么求？\n",
    "\n",
    "直接记住定理吧：lcm(a, b) = a * b / gcd(a, b)，其中gcd是计算最大公因数（Greatest Common Divisor）的函数。\n",
    "\n",
    "现在的问题是，最大公因数怎么求？这应该是经典算法了，我们一般叫辗转相除算法（或者欧几里得算法）。\n",
    "\n",
    "好了，套娃终于套完了，我们可以把上述思路翻译成代码就可以实现f函数，注意本题数据规模比较大，有时候需要用long类型防止int溢出：\n",
    "\n",
    "\"\"\"\n",
    "# 计算最大公因数（辗转相除/欧几里得算法）\n",
    "def gcd(a, b):\n",
    "    if a < b:\n",
    "        # 保证 a > b\n",
    "        return gcd(b, a)\n",
    "\n",
    "    if b == 0:\n",
    "        return a\n",
    "\n",
    "    return gcd(b, a % b)\n",
    "\n",
    "\n",
    "# 最小公倍数\n",
    "def lcm(a, b):\n",
    "    # 最小公倍数就是乘积除以最大公因数\n",
    "    return a * b / gcd(a, b)\n",
    "\n",
    "\n",
    "# 函数 f 是一个单调函数\n",
    "# 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字\n",
    "def f(num, a, b, c):\n",
    "    set_a = num // a\n",
    "    set_b = num // b\n",
    "    set_c = num // c\n",
    "    set_ab = num // lcm(a, b)\n",
    "    set_ac = num // lcm(a, c)\n",
    "    set_bc = num // lcm(b, c)\n",
    "    set_abc = num // lcm(lcm(a, b), c)\n",
    "    # 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C\n",
    "    return set_a + set_b + set_c - set_ab - set_ac - set_bc + set_abc\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        # 题目说本题结果在 [1, 2 * 10^9] 范围内，\n",
    "        # 所以就按照这个范围初始化两端都闭的搜索区间\n",
    "        left, right = 1, 2*10**9\n",
    "        # 搜索左侧边界的二分搜索\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if f(mid, a, b, c) < n:\n",
    "                # [1..mid] 中符合条件的元素个数不足 n，所以目标在右半边\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                # [1..mid] 中符合条件的元素个数大于 n，所以目标在左半边\n",
    "                right = mid - 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        '''\n",
    "        计算有多少个丑数小于等于x\n",
    "        x整除a,b,c -整除ab,bc,ac最小公倍数 +整除abc最小公倍数 即为所求\n",
    "        '''\n",
    "        def uglynum(x):\n",
    "            return x//a+x//b+x//c-x//(a*b//gcd(a,b))-x//(a*c//gcd(a,c))-x//(b*c//gcd(b,c))+x//lcm3(a,b,c)\n",
    "\n",
    "        # 三数最小公倍数=两数最小公倍数与第三个数的最小公倍数\n",
    "        def lcm3(x,y,z):\n",
    "            a = (x*y)//gcd(x,y)  \n",
    "            return (a*z)//gcd(a,z)\n",
    "        '''\n",
    "        二分搜索，注意只要uglynum(mid)<n left就=mid+1 所以最后得到的left就是所求\n",
    "        例如测试用例2中  a=2,b=3,c=4\n",
    "        括号中为丑数                    1,(2),(3),(4),5,(6),7,(8)\n",
    "        小于等于它们的丑数个数分别为     0, 1 , 2 , 3 ,3, 4, 4, 5 \n",
    "        若n==4\n",
    "        如果uglynum(mid)<4 则left一定能直接取到6而不是7\n",
    "        '''\n",
    "        left=1\n",
    "        right=n*min(a,b,c)\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if uglynum(mid)<n:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        ab, ac, bc, abc = lcm(a,b), lcm(a,c), lcm(b,c), lcm(lcm(a,b),c)\n",
    "\n",
    "        def getK(x):\n",
    "            return x//a + x//b + x//c - x//ab - x//ac - x//bc + x//abc\n",
    "        \n",
    "        l, r = 1, 2 * 10**9\n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            isOk = mid%a == 0 or mid%b == 0 or mid%c == 0\n",
    "            K = getK(mid)\n",
    "            if K < n:\n",
    "                l = mid + 1\n",
    "            elif K > n:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                if isOk:\n",
    "                    res = mid\n",
    "                    break\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        def gcd(a,b):\n",
    "            if (b):\n",
    "                return gcd(b, a % b)\n",
    "            else:\n",
    "                return a\n",
    "        def lcm(a,b):\n",
    "            return int(a*b//gcd(a,b))\n",
    "        def cnt(mid, a, b, c):\n",
    "            ab = int(lcm(a,b))\n",
    "            ac = int(lcm(a,c))\n",
    "            bc = int(lcm(b,c))\n",
    "            abc = int(lcm(a,lcm(b,c)))\n",
    "            return int(mid / a) + int(mid / b) + int(mid / c) - int(mid / ab) - int(mid / ac) - int(mid / bc) + int(mid /abc)\n",
    "        head = min(a,min(b,c))\n",
    "        tail = n* min(a, min(b,c))\n",
    "        while head <= tail:\n",
    "             mid = int((head + tail)//2)\n",
    "             if cnt(mid, a, b, c) == n:\n",
    "                 tail = mid - 1\n",
    "             elif cnt(mid, a, b, c) < n:\n",
    "                head = mid + 1\n",
    "             else:\n",
    "                 tail = mid - 1\n",
    "        return head   \n",
    "\n",
    "            \n",
    "            \n",
    "                \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "        \n",
    "        \n",
    "        ab=math.lcm(a,b)\n",
    "        ac=math.lcm(a,c)\n",
    "        bc=math.lcm(b,c)\n",
    "        abc=math.lcm(a,b,c)\n",
    "        def check(m):\n",
    "            cnt=0\n",
    "            cnt+=m//a\n",
    "            cnt+=m//b\n",
    "            cnt+=m//c\n",
    "            cnt-=m//ab\n",
    "            cnt-=m//ac\n",
    "            cnt-=m//bc\n",
    "            cnt+=m//abc\n",
    "            return cnt\n",
    "        \n",
    "        l=n\n",
    "        r=n*a\n",
    "\n",
    "        while l+1<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if check(mid)<n:\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        \n",
    "        if check(r)==n:\n",
    "            return r\n",
    "        else:\n",
    "            return l\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n",
    "\n",
    "        # 最小公倍数\n",
    "        lcm_ab, lcm_ac, lcm_bc = (a*b)//gcd(a, b), (a*c)//gcd(a,c), (b*c)//gcd(b, c)\n",
    "        lcm_abc = (lcm_ab*lcm_ac)//gcd(lcm_ab, lcm_ac)\n",
    "        # 通分的系数 \n",
    "        a_f, b_f, c_f = lcm_abc//a, lcm_abc//b, lcm_abc//c\n",
    "        ab_f, ac_f, bc_f = lcm_abc//lcm_ab, lcm_abc//lcm_ac, lcm_abc//lcm_bc\n",
    "        x = n*lcm_abc // (a_f + b_f + c_f - ab_f -ac_f -bc_f + 1)\n",
    "        m = x//a + x//b + x//c - x//lcm_ab - x//lcm_ac - x//lcm_bc + x//lcm_abc\n",
    " \n",
    "        if m < n:\n",
    "            x += min(a-x%a, b-x%b, c-x%c)\n",
    "        else:\n",
    "            x -= min(x%a, x%b, x%c)\n",
    "            if m -n > 0:\n",
    "                x -= min(x%a or a, x%b or b, x%c or c )\n",
    "         \n",
    "        return x"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
